tarjan有向图强联通分量 boj1606

宇宙建设 Submit: 71   Accepted:33 Time Limit: 1000MS  Memory Limit: 65536KDescription

laprovence最近很郁闷，于是他决心投身到宇宙交通建设中，来转移注意力，下面具体解释一下这个交通问题
比如说，有5个星球，从1可以到达2，并且从2可以到达3，从3可以到达1，那么可以把1，2，3
放入一个固定的区域中，对于这个区域中的每一星球（1，2，3）都可以到达这个区域中的其他星球。
laprovence很想知道如果给定了n个星球，并且告诉的其中每两个可以连通的星球，那么这些星球可以
被分为多少个区域，作为北邮的精英，你就帮助laprovence解决这个问题吧


Input
多组测试数据当n=0并且m=0时结束
第一行两个数n（n<=200)，m(m<=1000),n代表星球的个数，m表示可以连接的路径数
下面m行每行两个数a，b表示从a可以到达b


Output
这n个星球被分成的区域数

Sample Input

6 7
1 2
2 3
3 1
3 4
4 5
5 4
5 6


Sample Output

3

Hint
对于上面的例子6个星球被分为（1，2，3）（4,5）（6）三个区域

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

int n, m, Bcnt, Stop, Dindex, DFN[210], LOW[210], instack[210], stap[210], Belong[210];
vector<int> v_adj[210];

void init()
{
     int i;
     for(i=0; i<210; i++)
         v_adj[i].clear();
     
     memset(DFN, 0, sizeof(DFN));
     memset(LOW, 0, sizeof(LOW));
     memset(instack, 0, sizeof(instack));
     memset(Belong, 0, sizeof(Belong));
}

void tarjan(int i)
{
     int j;
     DFN[i] = LOW[i] = ++Dindex;
     instack[i] = true;
     stap[++Stop] = i;
     vector<int>::iterator begin, end;
     end = v_adj[i].end();
     for(begin=v_adj[i].begin(); begin != end; begin++)
     {
         j = *begin;
         if(!DFN[j])
         {
             tarjan(j);
             if(LOW[j] < LOW[i])
                 LOW[i] = LOW[j];
         }
         else if(instack[j] && DFN[j] < LOW[i])
             LOW[i] = DFN[j];
     }
     
     if(DFN[i] == LOW[i])
     {
         Bcnt++;
         do
         {
                j = stap[Stop--];
                instack[j] = false;
                Belong[j] = Bcnt;
         }while(j != i);
     }
}

void solve()
{
     int i;
     Bcnt = Stop = Dindex = 0;
     for(i=1; i<=n; i++)
     {
         if(!DFN[i])
             tarjan(i);
     }
     printf("%d\n", Bcnt);
}

int main(int argc, char *argv[])
{
    int i, a, b;
    
    while(1)
    {
        cin >> n >> m;
        if(0 == n && 0 == m)
            break;
        init();
        for(i=0; i<m; i++)
        {
            cin >> a >> b;
            v_adj[a].push_back(b);
        }
        solve();
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}