cojs 1298. 通讯问题

★   输入文件：jdltt.in   输出文件：jdltt.out   简单对比
时间限制：1 s   内存限制：128 MB

 /*先进行tarjan把所有的强连通分量放到几个数组中去，然后先对每个数组中的元素按字典序排序，然后把几个数组按照字典序排序，这样才能按照题目的意思输出*/

 #include<iostream>

 using namespace std;

 #include<cstring>

 #include<cstdio>

 #include<stack>

 stack<int>sta;

 #include<algorithm>

 #define N 120

 int dfn[N],low[N];

 int n,anst=;

 struct Ans{

     int a[N];

     void sor(){sort(a+,a+a[]+);}

 }ans[N];

 struct Edge{

     int v,last;

 }edge[N*N*];

 int topt=,t=;

 int head[N];

 bool visited[N]={},instack[N]={};

 void add_edge(int u,int v)

 {

     ++t;

     edge[t].v=v;

     edge[t].last=head[u];

     head[u]=t;

 }

 void input()

 {

     scanf("%d",&n);

     int u,v;

     while(scanf("%d%d",&u,&v)==)

     {

         add_edge(u,v);

     }

 }

 void tarjan(int k)/*tarjan算法，不解释*/

 {

     visited[k]=true;

     dfn[k]=low[k]=++topt;

     sta.push(k);

     instack[k]=true;

     for(int l=head[k];l;l=edge[l].last)

     {

         if(!visited[edge[l].v])

         {

             tarjan(edge[l].v);

             low[k]=min(low[k],low[edge[l].v]);

         }

         else {

             if(instack[edge[l].v])

               low[k]=min(low[k],dfn[edge[l].v]);

         }

     }

     if(low[k]==dfn[k])

     {

         anst++;

         int ys=sta.top();

         instack[ys]=false;

         sta.pop();

         while(ys!=k)

         {

             ans[anst].a[]++;

             ans[anst].a[ans[anst].a[]]=ys;

             ys=sta.top();

             instack[ys]=false;

             sta.pop();

         }

         instack[ys]=false;

         ans[anst].a[]++;

         ans[anst].a[ans[anst].a[]]=ys;

     }

 }

 int cmp(Ans p,Ans q)

 {

     for(int i=;i<=p.a[]&&i<=q.a[];++i)

     {

         if(p.a[i]<q.a[i])

           return true;

     }

     return false;

 }

 int main()

 {

     freopen("jdltt.in ","r",stdin);

     freopen("jdltt.out","w",stdout);

     input();

     for(int i=;i<=n;++i)

       if(!visited[i])

         tarjan(i);

     for(int i=;i<=anst;++i)

        ans[i].sor();/*对每个强连通分量的元素排序，注意结构体函数的妙用*/

     sort(ans+,ans+anst+,cmp);/*再把所有的强连通分量排序*/

     printf("%d\n",anst);

     for(int i=;i<=anst;++i)

     {

         for(int j=;j<=ans[i].a[];++j)

           printf("%d ",ans[i].a[j]);

         printf("\n");

     }

     fclose(stdin);fclose(stdout);

     return ;

 }