Cod sursa(job #1232951)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 24 septembrie 2014 12:50:29
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<cstdio>
#include<vector>
using namespace std;
vector<int> gno[200005],gin[200005];
int ord[200005],t,ncc,lu[200005],rez[200005],lt;
bool vi[200005];
struct sp
{
    int t,n;
}v[100005];
void viz(int nod)
{
  int j;
  for(j=gno[nod].size()-1;j>=0;j--)
  if(vi[gno[nod][j]]==0)
  {
      vi[gno[nod][j]]=1;
    viz(gno[nod][j]);
  }
  ord[++t]=nod;
}
void ctc(int nod)
{
    vi[nod]=1;
    int j;
    lu[ncc]++;
    lt++;
    rez[lt]=nod;
    for(j=gin[nod].size()-1;j>=0;j--)
        if(vi[gin[nod][j]]==0)
        {
        ctc(gin[nod][j]);
        }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m,i,x,y,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        gno[x].push_back(y);
        gin[y].push_back(x);
    }
    t=0;
    for(i=1;i<=n;i++)
    if(vi[i]==0)
    {
        vi[i]=1;
    viz(i);
    }
    for(i=1;i<=n;i++)
    vi[i]=0;
    ncc=lt=0;
    for(i=t;i>=1;i--)
    if(vi[ord[i]]==0)
    {
        ncc++;
    ctc(ord[i]);
    }
    j=1;
    printf("%d\n",ncc);
    for(i=1;i<=ncc;i++)
    {
        x=j+lu[i]-1;
    for(j=j;j<=x;j++)
    printf("%d ",rez[j]);
    printf("\n");
    }
    return 0;
}