第八章 图
边有方向，叫有向图，否则叫无向图
图G 节点V E边
有向图：
G = (V, E)
V(G) = {v1, v2, v3}
E(G) = {<v1, v2>, <v2, v3>}
无向图：
G = (V, E)
V(G) = {v1, v2, v3}
E(G) = {(v1, v2), (v2, v3)}
度：与该顶点相关联的边的个数
入读：指向这个节点的边的个数
出度：该节点指出去的边的个数
边数e
$$ e = 所有节点度数之和/2 $$
路径长度：这条路径上的边的个数
一个路径，如果除了起点和终点，其他节点均不相同，那么这个路径简单路径
如果起点和终点相同，其他节点均不相同，那么这个路径为简单回路，简单环
一个无向图中，任意两个节点之间均有路，那么这个图为连通图
连通分量: 一个无向图的最大联通子图
即一个不是连通图的无向图，有多个连通子图
在有向图G中，任意两个节点均有路，那么这个图为强连通图
有向图的极大连通子图为其强连通分量
8.3 图的基本存储结构
邻接矩阵
邻接表
8.4 图的遍历
深度优先遍历
广度优先遍历
8.5 生成树与最小生成树
对于一个无向连通图G=(V,E)，设G'为其一个子图，如果G'包含了所有节点，并且G'是一个无回路的连通图，那么G'是G的一棵生成树
最小生成树为所有生成树中路径长度最短的一棵生成树
prim算法
从已经在最小生成树集合的点出发，寻找新的最短边，加入新的点
kruskal算法
从所有的边中寻找最短边，如果这个边的两个点有任意一个不在最小生成树集合中，那么就可以加入这个边
prim具体的做法又有两种
第一种是我大学时课本的方法，用一个数组low来记录当前最小生成树中的点到不在树中的点的最短距离，每次从这个low数组中取出距离最小的一个边，加入到最小生成树，并且，用这个新加进来的点维护low数组即可。
第二种是我同学课本上的一种方法，通过动态调整最小生成树中边的存储位置，来用空间换时间，时间复杂度从o(n * n)降低到了o(n * (n-2))
下面给出一道poj的题目作为例子：http://poj.org/problem?id=1258
Agri-Net Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 85603 Accepted: 34950 Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course. Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms. Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm. The distance between any two farms will not exceed 100,000. Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem. Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms. Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
prim方法一：
// 最小生成树-prime.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#define MaxInt 0x3f3f3f3f
#define N 110
//创建map二维数组储存图表，low数组记录每2个点间最小权值，visited数组标记某点是否已访问
int map[N][N], low[N], visited[N];
int n;
int prim()
{
int i, j, pos, min, result = 0;
memset(visited, 0, sizeof(visited));
//从某点开始，分别标记和记录该点
visited[1] = 1; pos = 1;
//第一次给low数组赋值
for (i = 1; i <= n; i++)
if (i != pos) low[i] = map[pos][i];
//再运行n-1次
for (i = 1; i<n; i++)
{
//找出最小权值并记录位置
min = MaxInt;
for (j = 1; j <= n; j++)
if (visited[j] == 0 && min>low[j])
{
min = low[j]; pos = j;
}
//最小权值累加
result += min;
//标记该点
visited[pos] = 1;
//更新权值
for (j = 1; j <= n; j++)
if (visited[j] == 0 && low[j]>map[pos][j])
low[j] = map[pos][j];
}
return result;
}
int main()
{
freopen("D:/c++/dev-data/in.txt", "r", stdin);
int i, v, j, ans;
while (scanf("%d", &n) != EOF)
{
//所有权值初始化为最大
memset(map, MaxInt, sizeof(map));
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
{
scanf("%d", &v);
map[i][j] = map[i][j] = v;
}
ans = prim();
printf("%d\n", ans);
}
return 0;
}
prim方法2：
// 最小生成树-prim2.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MaxInt=0x3f3f3f3f;
const int N=110;
//创建map二维数组储存图表
int mmap[N][N];
int rode[N][3];
int n;
int prim()
{
// 点的编号从0到n-1
// rode数组用来存放最小生成树的n-1条边
// rode[i]表示到i这个点，用的是哪个边
// rode[i][0] 表示第i条边的起点
// rode[i][1] 表示第i条边的终点
// rode[i][2] 表示第i条边的长度
// 用第一个点初始化最小生成树的边
for (int i = 1; i <= n-1; i++)
{
rode[i][0] = 0;
rode[i][1] = i;
rode[i][2] = mmap[0][i];
}
// 确定n-1条边，但事实上确定好n-2条边后，最后一条边就被更新正确了，所以到n-2即可，不从rode[0]开始，一直到rode[n-2]
for (int i = 1; i <= n - 2; i++)
{
// 要确定第k条边，先假设当前在rode[k]这个位置的边是最短边
int min_len = rode[i][2];
// 用no记录最短的边是哪一条
int no = i;
// 遍历之后的边，找出当前剩下（不在最小生成树）的边中的最短边
for (int j = i + 1; j <= n - 1; j++)
{
if (rode[j][2] < min_len)
{
min_len = rode[j][2];
no = j;
}
}
// 把找到的最短的边放在rode[k]这个位置，确定下来这个边属于最小生成树
swap(rode[i][0], rode[no][0]);
swap(rode[i][1], rode[no][1]);
swap(rode[i][2], rode[no][2]);
// 用新引入的点更新剩下的边（到剩下的点的最短距离可能会因为这个新引入的点而需要更新）
int new_point = rode[i][1];
for (int j = i + 1; j <= n - 1; j++)
{
if (mmap[new_point][rode[j][1]] < rode[j][2])
{
rode[j][0] = new_point;
rode[j][2] = mmap[new_point][rode[j][1]];
}
}
}
int sum = 0;
for (int i = 1; i <= n - 1; i++)
{
sum += rode[i][2];
}
return sum;
}
int main()
{
freopen("D:/c++/dev-data/in.txt", "r", stdin);
int i, v, j, ans;
while (scanf("%d", &n) != EOF)
{
//所有权值初始化为最大
memset(mmap, MaxInt, sizeof(mmap));
for (i = 0; i <= n-1; i++)
for (j = 0; j <= n-1; j++)
{
scanf("%d", &v);
mmap[i][j] = mmap[i][j] = v;
}
ans = prim();
printf("%d\n", ans);
}
return 0;
}
其实思路基本一致，但个人感觉第一份代码写起来更顺畅一些，简单易懂。
kruskal代码：
// 最小生成树-kruskal.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 110;
//创建map二维数组储存图表
int mmap[maxn][maxn];
int F[maxn];
int n;
void init(int n)
{
for (int i = 0; i < n; i++)F[i] = i;
}
int Find(int x)
{
return F[x] == x ? x : F[x] = Find(F[x]);//f[x]=find(f[x])这样写有助于快速查找
}
void join(int a, int b)
{
int fa = Find(a);
int fb = Find(b);
if (fa != fb)
{
F[fb] = fa;
}
}
class Rode {
public:
int start,end,len;
Rode(int start, int end, int len):start(start), end(end), len(len) {};
bool operator < (const Rode &a) const { return this->len >a.len; };
};
int kruskal()
{
int sum = 0;
init(n);
priority_queue<Rode> all_rode;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (mmap[i][j] != inf)
{
all_rode.push(Rode(i, j, mmap[i][j]));
}
}
}
while(all_rode.size())
{
Rode t = all_rode.top();
all_rode.pop();
if (Find(t.start)!=Find(t.end))
{
sum += t.len;
join(t.start, t.end);
}
}
return sum;
}
int main()
{
freopen("D:/c++/dev-data/in.txt", "r", stdin);
int i, v, j, ans;
while (scanf("%d", &n) != EOF)
{
//所有权值初始化为最大
memset(mmap, inf, sizeof(mmap));
for (i = 0; i <= n - 1; i++)
for (j = 0; j <= n - 1; j++)
{
scanf("%d", &v);
mmap[i][j] = mmap[i][j] = v;
}
ans = kruskal();
printf("%d\n", ans);
}
return 0;
}
8.6 最短路径
8.6.1 单源最短路径 dijikstra算法
题目链接：https://uoj.ac/problem/622
这个题目灰常好的呀，题目数据量可以卡住floyd，并且dijikstra还要详细的优化一下才能过。
为了避免原链接失效我把题目抄过来：
题目：
这是一道模板题。
给定一张边权非负的有向图（可能存在重边自环），请求出点 S 到点 1∼n 的最短路长度。
输入格式 第一行三个个正整数 n,m,S，表示图中点数，边数，源点编号。
下面 m 行，每行三个整数 ui,vi,wi，表示存在一条 ui 到达 vi，边权为 wi 的边。
输出格式 一行 n 个整数，表示 S 点到每个点的最短路大小，若无法到达，则输出 -1。
样例一 input
5 10 1
3 4 2
2 3 4
1 2 1
2 4 2
4 5 8
5 2 10
4 2 7
3 3 10
2 2 1
3 2 1
output
0 1 5 3 11
限制与约定 对于所有数据，满足：
$1≤ui,vi,S≤n, 1≤n≤3×10^5, 1≤m≤10^6, 0≤wi≤10^9$。
时间限制：2s 空间限制：512MB
思路：
看一下数据范围
点的个数是3x1e5开数组肯定是开不下了，最先想到的是邻接表。
边的个数是1e6，假设一个边一个字节，1e6B/1024B=1e6/1e3MB=1e3MB,就是说512MB刚刚好存下所有的边。
w是1e9，并且在实际测试的时候也发现int装不下，用ll吧
在dijikstra算法中思路是将所有点分成两个集合，一个是已经找到了最短路径长度的点集合1，一个是没确定最短路径长度的集合2。
每次从所有连接了集合1和集合2的边中找到一条最短的边，那么可以确定这条边通往的新的点的路径长度是目前扩展新点所需要长度的最短长度。
那么到这个新点的最短路径长度就确定下来了。
可知我们需要存储这些连接集合1到集合2的边，并每次从这些边中找一个最短的。为了快速找到这个边，那么用一个小根堆是最方便的，即可以用优先队列priority_queue实现。
每次扩展一个点，我们都需要把这个新点所有可用的边遍历一下，找到那些连接着集合2的边，把这些边加入到存储边的优先队列中。
假如说一个新的点，扩展出来一条到x点的边，长度是x_len,但是目前优先队列中已经有一条到x点的边，边长还比x_len要小，那么就不用把这个边加入到队列中了，即占内存，又占插入这个边所用的时间。
在输入边的时候因为怕有重复的起始节点，但长度不同的边。我们需要记录下来最短的那个边，所以在输入边时我们也有快速查询的需求，这个可以用map实现。
详细代码：
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long ll;
ll n, m, s;
ll ss, ee, w;
const int maxn = 3 * 1e5 + 1;
ll dis[maxn], vis[maxn];
class Edge
{
public:
friend bool operator < (const Edge& a, const Edge& b);
ll end, len;
Edge(){this->end=-1;this->len=-1;}
Edge(ll end, ll len) :end(end), len(len){}
};
bool operator < (const Edge& a, const Edge& b)
{
return a.len > b.len;
}
map<ll, ll> mmap[maxn];
void dijikstra()
{
memset(dis, -1, sizeof(dis));
memset(vis, 0, sizeof(vis));
priority_queue<Edge> pri_queue_edge;
// 把起始节点加入到最短路径点集合中
pri_queue_edge.push(Edge(s, 0));
while(pri_queue_edge.size())
{
// 拿出从最短路径点集合到未在最短路径点集合的边中路径最短的边
Edge t = pri_queue_edge.top();
pri_queue_edge.pop();
if (vis[t.end])continue;
int new_point = t.end;
// 把这个新点的最短路径长度确定下来，并标记为在最短路径点集合中了
dis[new_point] = t.len;
vis[new_point] = 1;
// 遍历新点的所有边，找到可用的边加入到优先队列
map<ll, ll>::iterator it=mmap[new_point].begin();
for(it=mmap[new_point].begin();it!=mmap[new_point].end();it++)
{
ll new_dis = it->second+dis[new_point];
// 如果一个边所要到的点是在未在最短路径集合中的点，并且这个边到新点所用的距离比优先队列中可能存在的边要短，那么就把这个边加入到优先队列
if(!vis[it->first]&&(dis[it->first]==-1||new_dis<dis[it->first]))
{
dis[it->first]=new_dis;
pri_queue_edge.push(Edge(it->first, new_dis));
}
}
}
}
void init()
{
for(int i=0;i!=maxn;i++)mmap[i].clear();
}
int main()
{
freopen("D:/c++/dev-data/in.txt", "r", stdin);
while (~scanf("%d %d %d", &n, &m, &s))
{
init();
for (int i = 0; i != m; i++)
{
scanf("%d %d %d", &ss, &ee, &w);
if(!mmap[ss].contains(ee)||mmap[ss][ee]>w)mmap[ss][ee]=w;
}
dijikstra();
for (int i = 1; i <= n; i++)
{
if (i != 1)printf(" ");
printf("%lld", dis[i]);
}
printf("\n");
}
return 0;
}
8.6.2 多源最短路径 floyd算法
这个暂时没有找到什么好的例题。
暂时就用一道四川大学oj的一道吧，但是他们oj注册需要学号，估计没法提交测试。
题目链接地址：http://acm.scu.edu.cn//soj/problem.action?id=2427
题目
呆子是个没有方向感的人，经常在科大校园内迷路，所以他经常手里拿着一张 地图。每天呆子都在科大校园内转来转去，寻找新奇的人和事物，但是呆子 不是一个喜欢浪费时间的人，每次转悠的时候，他总想找到一条从起点到终点 的最短路。现在这个任务就交给了你，希望你给呆子设计一个查询系统， 呆子每次只需要输入起点和终点，你就要告诉呆子这两点间的最短路是什么。
输入
输入可能有多组。
每组输入的第一行包括两个数字 n和m，其中1 <= n <= 100，表示地图上 的路口的个数（呆子只会从一个路口到另外一个路口），0 <= m < n(n-1)/2， 表示图上的小路的个数，每条小路连接一对路口。
如果m > 0，那么后面将紧跟m行，每行包括三个整数，分别是这条路连接 的两个路口i,j(1<=i,j<=n)和这条路的长度L(1<=L<=1000)。
我们保证，输入的地图都是对的，而且没有两个路口之间存在两条或以上 的路，每条路的长度都是正的，还有这里的路都是双向的，没有一条路 是连接两个相同的路口。
紧接下来的一行是一个整数100000 > k > 0，表示有多少次查询。
紧接下来的k行，每行由两个整数i,j组成，表示查询这两个路口之间的最短路 的长度。(1 <= i,j <= n)
最后一组输入保证 n = 0, 这组输入不需要处理。
输出
对每组输入的每个查询，单独使用一行来输出查询结果：如果两个路口之间 存在一条路，输出其最短路的长度；否则输出“pity”（引号不用输出）。
每组输出使用一个空行作为结尾。
输入例子
3 3
1 2 1
2 3 1
1 3 1
2
1 2
1 3
3 3
1 2 1
2 3 1
1 3 1
2
1 2
1 3
0 0
输出例子
1
1
1
1
代码：
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
const int maxn=101;
int n,m,k;
int mmap[maxn][maxn];
int ss, ee, ww;
void floyd()
{
for(int mid=1;mid<=n;mid++)
{
for(int i=1;i<=n;i++)
{
if(mmap[i][mid]==-1)continue;
for(int j=1;j<=n;j++)
{
if(mmap[j][mid]==-1)continue;
int new_dis = mmap[i][mid]+mmap[j][mid];
if(mmap[i][j]==-1||new_dis<mmap[i][j])mmap[i][j]=new_dis;
}
}
}
}
int main()
{
freopen("D:/c++/dev-data/in.txt", "r", stdin);
while(~scanf("%d %d", &n, &m))
{
if(n==0||m==0)break;
memset(mmap, -1, sizeof(mmap));
for(int i=0;i!=m;i++)
{
scanf("%d %d %d", &ss, &ee, &ww);
mmap[ss][ee]=ww;
mmap[ee][ss]=ww;
}
floyd();
scanf("%d", &k);
for(int i=0;i!=k;i++)
{
scanf("%d %d", &ss, &ee);
if(mmap[ss][ee]==-1)printf("pity\n");
else printf("%d\n", mmap[ss][ee]);
}
printf("\n");
}
return 0;
}
板子：
#include<bits/stdc++.h>
using namespace std;
const int maxn=110;
int dp[maxn][maxn];
int n,m;
int s,e,d;
int minlen=0;//保存最短长度
void floyd()
{
int len=0;
//采用Floyd-Warshall算法
//思路是看i到j能否通过一些中间点来减少距离
//注意是一些点，但一会儿在代码中你可能会发现每次只是让其判断是否可以以k为中间点来缩减路径
//其实状态是可以叠加的，当以1为中间点优化完整个路径后，你再去观察整个路径数组
//会发现很多地方已经运用1邻接的路优化过了，那么接下来用 2进行优化时是在1号点优化的基础上进行优化的
//要想保证2号点可以在1号点的优化的基础上继续进行优化，那么需要注意循环k（中间点）的书写位置
//若将k的循环写在内层，那么你会发现，优化并不充分，原因见循环内部
for(int k=1;k<=n;k++) //k的循环写在外面可以实现优化的叠加
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
int d=-1;
if(i!=j&&dp[i][k]>0&&dp[k][j]>0)d=dp[i][k]+dp[k][j];
else d=dp[i][j];
if(dp[i][j]<0||dp[i][j]>d)dp[i][j]=d;
/*
for(int k=1;k<=n;k++)
若将k的循环写在内层你会发现在用2进行优化时1的有一些优化还没有遍历到，
例如，在1到2利用k点优化完成后，你再也无法用后面的路径来优化1到2了，
这就造成了优化不充分
但是如果在外面，你会发现在用1进行优化时也不充分，因为用不到2-n号点优化的成果
但是，在用2号点进行优化时可以充分利用一号点，这时你会发现当用1号点进行优化时
不能用到2号点成果的遗憾被弥补了回来 ，同样3号点也能弥补3号点不在时的优化遗憾
最后n号点优化完成，所有的遗憾也就被弥补完成了
*/
}
}
}
}
void clear()
{
memset(dp,-1,sizeof(dp));
for(int i=1;i<=n;i++)
{
dp[i][i]=0;
}
}
int main()
{
scanf("%d %d",&n,&m);
clear();//预处理-1表示路径不存在
for(int i=0;i!=m;i++)
{
scanf("%d %d %d",&s,&e,&d);
dp[s][e]=d;
}
floyd();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cout<<dp[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
8.7 拓扑排序
用于对有前置要求的工作进行排序。
比如说大小的先修课修完之后才能学之后的专业课。
有的要求给出一个合适的顺序，一般不唯一，有的让判断是否存在一个可行的方案，这个是来判断这个有向图中是否存在环。
leetcode上的一道题目：https://leetcode.cn/problems/course-schedule/
题目：
207 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
分析：
这道题只是问是否可行，那么只要课程之间不存在矛盾的环就好了，如果用深搜的方法，那么只要每次的遍历不会重复遍历到同一个节点就好，就是用一个vis数组标记一下这次深搜过程中所经过的点，整个深搜结束不存在一个点被在一次搜索中被访问两次即可。
但是由于点的个数较多，边的数量也不少，有5000个，假如恰巧组成一个大环，有可能会导致爆栈，所以数据量较大时不太适合用深搜。
可以考虑每个点的入度，就是有多少个点是他的前置节点，每次找到一个没有前置节点的点删除，并把这个点的后续节点的入度减1，指到再找不到入度为0的前置节点，如果此时删除了全部节点，那么说明不存在环，否则存在，可知如果使用for循环遍历寻找入度为0的节点，那么会较为占用时间，我们可以在删除一个节点，并将后续节点入度减一这里判断是否出现了新的入度为0 的节点，如果有就假如队列，这样就用存储的方式加快了寻找入度为0 的节点。可以看出本质上是个广搜的方法。
代码：
(提示：代码中的map判断一个元素是否存在可用contains这个函数，但是这个需要c++>=20，用find会导致如果元素不存在，那么会创建一个这样的键值，导致map实际的树变大，搜索速度降低，但是数据量小时影响也不大)
#include "stdafx.h"
#include<iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
using namespace std;
int numCourses, prerequisites_cnt;
int ss, ee;
vector<vector<int>> prerequisites;
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
int* cnt = (int*)malloc(numCourses * sizeof(int));
memset(cnt, 0, numCourses * sizeof(int));
map<int, vector<int>> mmap;
for (int i = 0; i != prerequisites.size(); i++)
{
int _s = prerequisites[i][0], _e = prerequisites[i][1];
cnt[_e]++;
if (mmap[_s].size()==0||mmap[_s].size())mmap[_s].push_back(_e);
}
queue<int> q;
for (int i = 0; i != numCourses; i++)if (cnt[i] == 0)q.push(i);
bool flag = 1;
int check_cnt = 0;
while (q.size())
{
int no = q.front();
q.pop();
check_cnt++;
cnt[no]--;
for (int i = 0; i != mmap[no].size(); i++)
{
int _e = mmap[no][i];
cnt[_e]--;
if (cnt[_e] == 0)q.push(_e);
if (cnt[_e] < 0)flag = false;
}
if (!flag)break;
}
free(cnt);
return check_cnt==numCourses;
}
int main()
{
freopen("D:/c++/dev-data/in.txt", "r", stdin);
while (~scanf("%d", &numCourses))
{
prerequisites.clear();
scanf("%d", &prerequisites_cnt);
for (int i = 0; i != prerequisites_cnt; i++)
{
scanf("%d %d", &ss, &ee);
vector<int> _v;
_v.push_back(ss);
_v.push_back(ee);
prerequisites.push_back(_v);
}
bool flag = canFinish(numCourses, prerequisites);
if (flag)printf("true\n");
else printf("false\n");
}
return 0;
}