poj 2186【Popular Cows】1236【Network of Schools】2553【The Bottom of a Graph】

三种方法求极大强连通分支的算法，一题一种方法

poj 2186 求牛被所有其它的牛崇拜的个数，在一个强连通分量里面的牛是互相崇拜的，所以如果这个强连通分支被其它牛崇拜那么这里面的牛都被其它牛崇拜.。。。这一题我用的Tarjan算法

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <vector>
 4 using namespace std;
 5 
 6 const int maxN = 10000+10;
 7 int low[maxN];
 8 int stack[maxN],top;
 9 int DFN[maxN];
10 int cnt;
11 int del[maxN];
12 vector<int> edge[maxN];
13 int num;
14 bool in[maxN];
15 
16 void Tarjin(int x)
17 {
18     stack[top ++] = x;
19     low[x] = cnt;
20     DFN[x] = cnt ++;
21 
22     int len = edge[x].size();
23     for(int i = 0;i < len;i ++)
24     {
25         int u = edge[x][i];
26         if(!DFN[u])
27         {
28             Tarjin(u);
29             if(low[x] > low[u]) low[x] = low[u];
30         }
31         else if(!del[u])
32         {
33             if(low[x] > DFN[u]) low[x] = DFN[u];
34         }
35     }
36 
37     if(low[x] == DFN[x])
38     {
39         num ++;
40         do{
41             del[stack[top-1]] = num;
42         }while(stack[--top] != x);
43     }
44 }
45 
46 int main()
47 {
48     int n,m;
49     cin >> n >> m;
50     for(int i = 0;i < m;i ++)
51     {
52         int u,v;
53         cin >> u >> v;
54         edge[v].push_back(u);
55     }
56     memset(DFN,0,sizeof(DFN));
57     top = 0;
58     cnt = 1;
59     num = 0;
60 
61     for(int i = 1;i <= n;i ++)
62     {
63         if(!DFN[i])
64         {
65             Tarjin(i);
66         }
67     }
68         memset(in,false,sizeof(in));
69         for(int i = 1;i <= n;i ++)
70         {
71             int len = edge[i].size();
72             for(int j = 0;j < len;j ++)
73             {
74                 if(del[i] != del[edge[i][j]])
75                     in[del[edge[i][j]]] = true;
76             }
77         }
78         int count = 0;
79         for(int i = 1;i <= num;i ++)
80         {
81             if(!in[i])
82                 count ++;
83         }
84         if(count > 1)
85         {
86             cout << "0" << endl;
87             return 0;
88         }
89         count = 0;
90         for(int i = 1;i <= n;i ++)
91         {
92             if(!in[del[i]])
93                 count ++;
94         }
95 
96         cout << count << endl;
97 
98     return 0;
99 }

poj 1236 http://www.cppblog.com/mythit/archive/2009/05/25/85718.html 用的Kosaraju算法

View Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <vector>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 const int maxlen = 110;
  8 vector<int> edge[maxlen];
  9 vector<int> redge[maxlen];
 10 bool vis[maxlen];
 11 int twig[maxlen];
 12 int Search[maxlen];
 13 bool in[maxlen],out[maxlen];
 14 int N;
 15 int cnt;
 16 
 17 void dfs1(int i)
 18 {
 19     vis[i] = true;
 20     int len = edge[i].size();
 21     for(int j = 0;j < len;j ++)
 22     {
 23         if(!vis[edge[i][j]])
 24         {
 25             //vis[edge[i][j]] = true;
 26             dfs1(edge[i][j]);
 27         }
 28     }
 29     Search[cnt ++] = i;
 30 }
 31 
 32 void dfs2(int i)
 33 {
 34     vis[i] = true;
 35     twig[i] = cnt;
 36     int len = redge[i].size();
 37 
 38     for(int j = 0;j < len;j ++)
 39     {
 40         int x = redge[i][j];
 41         if(!vis[x])
 42         {
 43             //vis[x] = true;
 44             dfs2(x);
 45         }
 46     }
 47 }
 48 
 49 void Kosaraju()
 50 {
 51     memset(vis,false,sizeof(vis));
 52     cnt = 0;
 53     for(int i = 1;i <= N;i ++)
 54     {
 55         if(!vis[i])
 56             dfs1(i);
 57     }
 58 
 59     cnt = 0;
 60     memset(vis,false,sizeof(vis));
 61     for(int i = N-1;i >= 0;i --)
 62     {
 63         if(!vis[Search[i]])
 64         {
 65             cnt ++;
 66             dfs2(Search[i]);
 67         }
 68     }
 69 
 70 }
 71 
 72 int main()
 73 {
 74     cin >> N;
 75     for(int i = 0;i <= N;i ++)
 76         redge[i].clear();
 77 
 78     for(int i = 1;i <= N;i ++)
 79     {
 80         edge[i].clear();
 81         int x;
 82         while(cin >> x,x)
 83         {
 84             edge[i].push_back(x);
 85             redge[x].push_back(i);
 86         }
 87     }
 88 
 89     Kosaraju();
 90     memset(in,false,sizeof(in));
 91     memset(out,false,sizeof(out));
 92     for(int i = 1;i <= N;i ++)
 93     {
 94         int len = edge[i].size();
 95         for(int j = 0;j < len;j ++)
 96         {
 97             if(twig[i] != twig[edge[i][j]])
 98             {
 99                 out[twig[i]] = true;
100                 in[twig[edge[i][j]]] = true;
101             }
102         }
103     }
104     int ans1 = 0,ans2 = 0;
105     for(int i = 1;i <= cnt;i ++)
106     {
107         if(!out[i]) ans1 ++;
108         if(!in[i]) ans2 ++;
109     }
110     if(cnt == 1)
111     {
112         cout << "1\n" << "0" << endl;
113     }
114     else
115     {
116         cout << ans2 << "\n" << max(ans2,ans1) << endl;
117     }
118 
119     return 0;
120 
121 }

poj 2553 一个点如果可以到达其它的点则必须那个点也可以到达这个点，那么不到达那么点，要么互达。。。我用的是Gabow算法

View Code

  1 #include <iostream>
  2 #include <cstring>
  3 #include <vector>
  4 using namespace std;
  5 
  6 const int maxN = 5000+10;
  7 vector<int> edge[maxN];
  8 int stack1[maxN],top1;
  9 int stack2[maxN],top2;
 10 int del[maxN];
 11 int Time[maxN];
 12 //bool vis[maxN];
 13 int cnt;
 14 int num;
 15 int n,m;
 16 bool out[maxN];
 17 int ans[maxN];
 18 
 19 void Gabow(int x)
 20 {
 21     //vis[x] = true;
 22     stack1[top1 ++] = x;
 23     stack2[top2 ++] = x;
 24     Time[x] = cnt ++;
 25     del[x] = 0;
 26 
 27     int len = edge[x].size();
 28     for(int i = 0;i < len;i ++)
 29     {
 30         int u = edge[x][i];
 31         if(!Time[u])
 32         {
 33             Gabow(u);
 34         }
 35         else if(!del[u])
 36         {
 37             while(Time[stack2[top2-1]] > Time[u])
 38             {
 39                 top2 --;
 40             }
 41         }
 42     }
 43 
 44     if(stack2[top2-1] == x)
 45     {
 46         num ++;
 47         top2 --;
 48         do{
 49             del[stack1[top1-1]] = num;
 50         }while(stack1[--top1] != x);
 51     }
 52 }
 53 
 54 int main()
 55 {
 56     while(cin >> n,n)
 57     {
 58         cin >> m;
 59         for(int i = 0;i <= n;i ++)
 60             edge[i].clear();
 61 
 62         for(int i = 0;i < m;i ++)
 63         {
 64             int u,v;
 65             cin >> u >> v;
 66             edge[v].push_back(u);
 67         }
 68 
 69         memset(Time,0,sizeof(Time));
 70         top1 = 0;
 71         top2 = 0;
 72         cnt = 1;
 73         num = 0;
 74         //memset(vis,false,sizeof(vis));
 75         for(int i = 1;i <= n;i ++)
 76         {
 77             if(!Time[i])
 78                 Gabow(i);
 79         }
 80         //memset(vis,false,sizeof(vis));
 81         memset(out,false,sizeof(out));
 82         for(int i = 1;i <= n;i ++)
 83         {
 84             int len = edge[i].size();
 85             for(int j = 0;j < len;j ++)
 86             {
 87                 if(del[i] != del[edge[i][j]])
 88                 {
 89                     out[del[edge[i][j]]] = true;
 90                 }
 91             }
 92         }
 93         int t = 0;
 94         for(int i = 1;i <= n;i ++)
 95         {
 96             if(!out[del[i]])
 97             {
 98                 ans[t ++] = i;
 99             }
100         }
101         for(int i = 0;i < t-1;i ++)
102         {
103             cout << ans[i] << " ";
104         }
105         if(t >= 1)
106             cout << ans[t-1];
107         cout << endl;
108     }
109 
110     return 0;
111 }