Hdu 1269 【强连通分量】.cpp

题意：

给出一些两个门连通的关系

问是否所有房间都连通

输入：

　　n m 表示n个房间 m个关系

　　接下来m行a b 表示房间a和房间b 相连

如果房间是互通的输出yes 否则 no

思路：

　　用tarjan求强连通分量

　　<强连通分量：有向图中任意两个点存在互通的道路..>

Tips：

　　强连通分量tarjan算法讲解：http://www.byvoid.com/blog/scc-tarjan/zh-hant/

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int MAXN = 10010;
 6 #define clr(x) memset(x, 0, sizeof(x))
 7 
 8 struct Edge
 9 {
10     int to;
11     int next;
12 }edge[1000010];
13 int head[MAXN];
14 int tot;
15 
16 void add(int s, int u)
17 {
18     edge[tot].to = u;
19     edge[tot].next = head[s];
20     head[s] = tot++;
21 
22  //   edge[tot].to = s;
23  //   edge[tot].next = head[u];
24   //  head[u] = tot++;
25 }
26 
27 int dfn[MAXN], low[MAXN];
28 int stack[MAXN], ins[MAXN], col[MAXN];
29 int ti, top, cnt;
30 int n, m;
31 
32 void tarjan(int u)
33 {
34     int i, k;
35     dfn[u] = low[u] = ++ti;
36     ins[u] = 1;
37     stack[++top] = u;
38     for(i = head[u]; i != -1; i = edge[i].next)
39     {
40         k = edge[i].to;
41         if(dfn[k] == 0) {
42             tarjan(k);
43             low[u] = min(low[u], low[k]);
44         } else if (ins[k]) {
45             low[u] = min(low[u], dfn[k]);
46         }
47     }
48     if(low[u] == dfn[u])
49         cnt++;
50 }
51 
52 void solve()
53 {
54     ti = cnt = top = 0;
55     clr(dfn);
56     for(int i = 1; i <= n; ++i)
57     if(!dfn[i])
58         tarjan(i);
59 }
60 
61 int main()
62 {
63     int i, j, k;
64     int a, b;
65     while(scanf("%d %d", &n, &m) != EOF)
66     {
67         if(n == 0 && m == 0) break;
68 
69         memset(head, 0xff, sizeof(head));
70         tot = 0;
71 
72         while(m--) {
73             scanf("%d %d", &a, &b);
74             add(a, b);
75         }
76 
77         solve();
78 
79         if(cnt == 1) puts("Yes");
80         else puts("No");
81     }
82     return 0;
83 }

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1269