POJ1236_A - Network of Schools _强连通分量::Tarjan算法

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<vector>
  5 
  6 using namespace std;
  7 
  8 const int maxn = 100 + 10;
  9 
 10 int N;
 11 int In[maxn], Out[maxn];
 12 
 13 /***************************Tarjan算法模板***************************/
 14 vector<int> G[maxn];
 15 int Mark[maxn], Root[maxn], Stack[maxn];//时间戳，根(当前分量中时间戳最小的节点)，栈
 16 bool Instack[maxn]; //是否在栈中标记
 17 int Ssc[maxn];            //每个节点所在的强连通分量的编号
 18 int Index, Ssc_n, Top;    //搜索时用的时间戳，强连通分量总数，栈顶指针
 19 
 20 void Tarjan(int u)        //u 当前搜索到的点
 21 {
 22     Mark[u] = Root[u] = ++ Index;  //每找到一个点，对时间戳和根初始化
 23     Stack[Top ++] = u;        //压栈
 24     Instack[u] = true;        //在栈中标记
 25 
 26     int v;
 27 
 28     for(int i= 0; i< G[u].size(); i++)   //向下搜索
 29     {
 30         v = G[u][i];
 31         if(Mark[v] == 0)                 //没到过的点
 32         {
 33             Tarjan(v);  //先向下搜索
 34             if(Root[u] > Root[v]) Root[u] = Root[v];//更新根
 35         }
 36         else if(Instack[v] && Root[u] > Mark[v]) Root[u] = Mark[v];  //到过的点且点仍在栈中，试着看这个点能不能成为根
 37     }
 38 /*对当前点的搜索结束*/
 39     if(Mark[u] == Root[u])  //当前点本身时根
 40     {
 41         Ssc_n ++;   //更新强连通分量数
 42 
 43         do{    //栈中比它后入栈的元素在以它为根的强连通分量中
 44             v = Stack[-- Top];
 45             Instack[v] = false;
 46             Ssc[v] = Ssc_n;//把同一个强连通分支的点做上相同标记 
 47         }while(v != u);    //直到它自己
 48     }
 49 }
 50 
 51 void SSC()
 52 {
 53     memset(Mark, 0, sizeof Mark);   //初始化时间戳和栈内标记
 54     memset(Instack, false, sizeof Instack);
 55     Index = Ssc_n = Top = 0;   //初始化时间戳，强连通分量数，栈顶指针
 56 
 57     for(int i= 1; i<= N; i++)   //保证图上所有点都访问到
 58         if(Mark[i] == 0) Tarjan(i);
 59 }
 60 /***************************Tarjan算法模板***************************/
 61 
 62 int main()
 63 {
 64     //freopen("in.txt", "r", stdin);
 65 
 66     scanf("%d", &N);
 67     for(int i= 1; i<= N; i++)
 68     {
 69         int x;
 70         while(scanf("%d", &x), x)
 71             G[i].push_back(x);
 72     }
 73 
 74     SSC();
 75 
 76     if(Ssc_n == 1)  //只有一个强连通分量的情况
 77     {
 78         cout << "1\n0\n";
 79         return 0;
 80     }
 81 
 82     memset(In, 0, sizeof In); //求每个强连通分量的入度和出度
 83     memset(Out, 0, sizeof Out);
 84     for(int u= 1; u<= N; u++)
 85     {
 86         for(int i= 0; i< G[u].size(); i++)
 87         {
 88             int v = G[u][i];
 89             if(Ssc[u] != Ssc[v])//u,v两点不在同一个强连通分支 
 90                 Out[Ssc[u]] ++, In[Ssc[v]] ++;
 91         }
 92     }
 93 
 94     int S1 = 0, S2 = 0;//找入度为0、出度为0的点的数目
 95     for(int i= 1; i<= Ssc_n; i++)
 96     {
 97         if(In[i] == 0) S1 ++;
 98         if(Out[i] == 0) S2 ++;
 99     }
100 
101     cout << S1 << endl << max(S1, S2) << endl;
102 
103     return 0;
104 }