Cod sursa(job #2145265)

Utilizator mateibanuBanu Matei Costin mateibanu Data 27 februarie 2018 11:12:46
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

#define NMAX 100010

int n,m,k,in=1;

vector<int>l[NMAX];
vector<int>lt[NMAX];
vector<int>r[NMAX];
int viz[NMAX],s[NMAX];

void df1(int x){
    int i,nr;
    viz[x]=1;
    nr=l[x].size();
    for (i=0;i<nr;i++)
    if (!viz[l[x][i]]){
        df1(l[x][i]);
    }
    s[++k]=x;
}

void df2(int x){
    int i,nr;
    r[in].push_back(x);
    viz[x]=1;
    nr=lt[x].size();
    for (i=0;i<nr;i++)
    if (!viz[lt[x][i]]){
        df2(lt[x][i]);
    }
}

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int i,x,y,j,nr;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        l[x].push_back(y);
        lt[y].push_back(x);
    }

    for (i=1;i<=n;i++)
    if (!viz[i]){
        k=0;
        df1(i);
        memset(viz,0,sizeof(viz));
        for (j=n;j>=1;j--)
            if (!viz[s[j]]) {df2(s[j]);in++;}
    }
    in--;
    printf("%d\n",in);
    for (i=1;i<=in;i++)
    {
        nr=r[i].size();
        for (j=0;j<nr;j++) printf("%d ",r[i][j]);
        printf("\n");
    }
    return 0;
}