题意:
为了让他们的儿子变得更勇敢些,Jiajia和Wind将他们带到一个大洞穴中。洞穴中有n个房间,有一些单向的通道连接某些房间。每次,Wind选择两个房间x和y,要求他们的一个儿子从一个房间走到另一个房间,这个儿子可以从x走到y,也可以从y走到x。Wind保证她布置的任务是可以完成的,但她确实不知道如何判断一个任务是否可以完成。为了使 Wind 下达任务更容易些,Jiajia决定找这样的一个洞穴,每对房间(设为x和y)都是相通(可以从x走到y,或者可以从 y 走到 x)的。给定一个洞穴,你能告诉 Jiajia,Wind
是否可以任意选择两个房间而不用担心这两个房间可能不相通吗?
输入描述:
输入文件的第1行为一个整数T,表示测试数据的个数。接下来有T个测试数据。 每个测试数据的第1行为两个整数n和m,0<n<1001,m<6000,分别表示洞穴中的房间数和通道数。接下来有m行,每行为两个整数u和v,表示房间从房间u到v有一条单向通道。
输出描述:
对每个测试数据,如果洞穴具备题目中提到的属性,输出'Yes',否则输出'No'。
样例输入:
1
8 11
1 2
2 3
2 5
2 6
3 5
4 3
5 2
5 4
6 7
6 8
7 6
样例输出:
Yes
本题虽然求解的是单连通性,但首先要转换成强连通分量的求解。这是因为,强连通分量中的顶点间存在双向的路径,因此可以将每个强连通分量收缩成一个新的顶点。在有向图的处理中经常需要将强连通分量收缩成一个顶点。
以样例输入中的测试数据为例,图8.22(a)描述了该测试数据。在图(b)中,将2个强连通分量各收缩成1个新的顶点。
强连通分量收缩后,再求其拓扑排序。 假设求得的拓扑序存储在 topo[MAX]中,topo[i]与topo[i+1]存在边连通(i 到i+1 或i+1 到i) ,则定有i 到i+1 的边。而如果每个topo[i]与topo[i+1]都存在边连通(即有i到i+1的边)时,topo[i]到任意topo[j]便都有边连通。
(摘自王桂平、王衍、任嘉辰《图论算法理论、实现及应用》)
看完书上所写,终于弄明白了缩点,就是把强连通分量简化成一个点,如果一个缩点A可以到达另一个缩点B,则这个强连通分量内所有的点都可以到达缩点B,并且可以到达缩点B的强连通分量中所有的点。不过感觉书上的代码有些矬,没有用。这是我的AC代码。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 1010 #define eps 1e-7 #define INF 0x3F3F3F3F //0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 1313131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxm = 6100; struct node{ int u, v, next; }edge[maxm],edge1[maxm]; int Stack[MAXN]; int head[MAXN], head1[MAXN], dfn[MAXN], low[MAXN], sccno[MAXN]; int scc_cnt, id, cnt, cnt1, top, n, m; void add_edge(int u, int v, node edge[], int head[], int &cnt){ edge[cnt].u = u; edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++; } void tarjin(int u){ int i, j; dfn[u] = low[u] = ++id; Stack[top++] = u; for(i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].v; if(dfn[v] == -1){ tarjin(v); low[u] = min(low[u], low[v]); } else if(!sccno[v]){ low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]){ scc_cnt++; int temp; do{ temp = Stack[--top]; sccno[temp] = scc_cnt; }while(temp != u); } } int Queue[MAXN]; int D[MAXN]; bool topo_sort(){ int i, j; int fr = 0, re = 0; for(i = 1; i <= scc_cnt; i++){ if(D[i] == 0) Queue[re++] = i; } if(re == 0 || re - fr > 1) return false; while(fr < re){ int u = Queue[fr++]; for(i = head1[u]; i != -1; i = edge1[i].next){ int v = edge1[i].v; D[v]--; if(D[v] == 0) Queue[re++] = v; } if(re - fr > 1) return false; } return true; } int main(){ int i, j, t; scanf("%d", &t); while(t--){ cnt = scc_cnt = id = top = cnt1 = 0; memset(head, -1, sizeof(head)); memset(head1, -1, sizeof(head1)); memset(dfn, -1, sizeof(dfn)); memset(sccno, 0, sizeof(sccno)); memset(D, 0, sizeof(D)); scanf("%d%d", &n, &m); for(i = 0; i < m; i++){ int u, v; scanf("%d%d", &u, &v); add_edge(u, v, edge, head, cnt); } for(i = 1; i <= n; i++){ if(dfn[i] == -1) tarjin(i); } if(scc_cnt == 1){ puts("Yes"); continue; } for(i = 0; i < cnt; i++){ int u = edge[i].u; int v = edge[i].v; if(sccno[u] != sccno[v]){ D[sccno[v]]++; add_edge(sccno[u], sccno[v], edge1, head1, cnt1); } } if(topo_sort()) puts("Yes"); else puts("No"); } return 0; }