题目大意：

例如：A跟B打电话,B跟C打电话,C跟A打电话..D跟E打电话,E跟D不打电话.则A,B,C属于同一个电话圈，D，E分别属于一个电话圈，问有多少个电话圈。

分析

就是裸的求强连通分量，直接用Tarjan解决

代码

#include <set>

#include <queue>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <map>

#include <string>

#include <stack>

using namespace std;

int N,M;

string NAME[40];

map<string,int> dict;

stack<int> S;

int tot=0;              //这一道题特有的存点..

int cnt=0;              //强连通数目

int TIME=0;             //时间戳

int DFN[40],Low[40];    //DNF 时间戳,Low ,u及u的子树最小的时间戳

bool INSTACK[40];       //判断是否在栈内

int Belong[40];         //存储属于哪一个强连通分量;

struct Edge{

    int to;

    Edge *next;

}E[20000],*EE;

struct Node{

    Edge *first;

}G[50];

void Link(int a,int b)

{

    EE->to=b;EE->next=G[a].first;G[a].first=EE++;

}

void input()

{

    EE=E;

    tot=0;

    TIME=0;

    cnt=0;

    string a,b;

    dict.clear();

    memset(G,0,sizeof(G));

    memset(DFN,0,sizeof(DFN));

    for(int i=1;i<=M;i++)

    {

        cin>>a>>b;

        if(dict[a]==0)

        {

            dict[a]=++tot;

            NAME[tot]=a;

        }

        if(dict[b]==0)

        {

            dict[b]=++tot;

            NAME[tot]=b;

        }

        Link(dict[a],dict[b]);

    }

}

void Tarjan(int u)

{

    DFN[u]=Low[u]=++TIME;

    S.push(u);

    INSTACK[u]=true;

    for(Edge *p=G[u].first;p;p=p->next)

    {

            if(DFN[p->to]==0)

            {

                Tarjan(p->to);

                Low[u]=min(Low[u],Low[p->to]);

            }

            else if(INSTACK[p->to]==true)

            Low[u]=min(Low[u],DFN[p->to]);

    }

    int k;

    if(DFN[u]==Low[u])

    {

            int ok=0;

            cnt++;

            do

            {

                k=S.top();

                S.pop();

                INSTACK[k]=false;

                Belong[k]=cnt;

                if(ok==0)

                {

                    ok=1;

                    cout<<NAME[k];

                }

                else cout<<", "<<NAME[k];

            }while(k!=u);

            cout<<endl;

    }

}

void solve()

{

    for(int i=1;i<=N;i++)

    {

        if(DFN[i]==0)

        Tarjan(i);

    }

}

int main()

{

    int CASE=0;

//  freopen("a.in","r",stdin);

    while(cin>>N>>M&&(N||M))

    {

        printf("Calling circles for data set %d:\n",++CASE);

        input();

        solve();

    }

}