Cod sursa(job #1252723)

Utilizator andreey_047Andrei Maxim andreey_047 Data 31 octombrie 2014 09:09:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <iostream>
#include <cstdio>
#include <vector>
#define nmax 100009
using namespace std;
int n,m,v[nmax],viz[nmax],fol[nmax],vt[nmax],uz[nmax],nr,sol[nmax];
vector<int>G[nmax],Gt[nmax];
void dfstf(int x){
 viz[x]=1;
  for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
   if(!viz[*it]) dfstf(*it);
  v[++v[0]]=x;
}
void dfs(int x){
 fol[x]=1;
 for(vector<int>::iterator it=Gt[x].begin();it!=Gt[x].end();it++)
  if(!fol[*it]) dfs(*it);
  uz[x]=1;
  vt[++vt[0]]=x;
}
int main(){
    int i,x,y,j;
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
      scanf("%d%d",&x,&y);
      G[x].push_back(y);
      Gt[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    if(!viz[i])
    dfstf(i);
    for(i=v[0];i>=1;i--)
     if(!uz[v[i]])
     {
          nr++;
          vt[0]=0;
         dfs(v[i]);
     }
     cout<<nr<<'\n';
     for(i=1;i<=v[0];i++)
      uz[v[i]]=fol[v[i]]=0;
    for(i=v[0];i>=1;i--)
     if(!uz[v[i]])
     {
          vt[0]=0;
         dfs(v[i]);
         for(j=1;j<=vt[0];j++)
          cout<<vt[j]<<' ';
        cout<<'\n';
     }
    return 0;
}