Cod sursa(job #1370366)

Utilizator avaspAva Spataru avasp Data 3 martie 2015 14:08:37
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<vector>
using namespace std;
int cate,n,m,a,b,k;
vector<int>v[100001],v1[100001],cmp[100001];
bool viz[100001],viz2[100001];
int st[100001];
void dfs1(int nod){
    viz[nod]=true;
    for(int i=0;i<v[nod].size();i++)
        if(viz[v[nod][i]]==false)
            dfs1(v[nod][i]);
    st[++k]=nod;
}

void dfs2(int nod){
    viz2[nod]=true;
   // printf("%d ",nod);
   cmp[cate].push_back(nod);
    for(int i=0;i<v1[nod].size();i++)
        if(viz[v1[nod][i]]==true&&viz2[v1[nod][i]]==false)
            dfs2(v1[nod][i]);
}
int main(){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        v[a].push_back(b);
        v1[b].push_back(a);
    }
    cate=0;
    for(int i=1;i<=n;i++)
        if(viz[i]==false){
            k=0;
            dfs1(i);
            for(int j=1;j<=n;j++)
                viz2[j]=false;
            for(int j=k;j>=1;j--){
                if(viz2[st[j]]==false){
                    cate++;
                    dfs2(st[j]);
                   // printf("\n");
                }
            }
        }
    printf("%d\n",cate);
    for(int i=1;i<=cate;i++){
        for(int j=0;j<cmp[i].size();j++)
            printf("%d ",cmp[i][j]);
        printf("\n");
    }
    return 0;
}