Cod sursa(job #1526322)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 16 noiembrie 2015 09:24:39
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> g[100010],gt[100010],components[100010];
int seen[100010],order[100010],cnt,comp;
void dfs(int node){
    int i,dim=g[node].size();
    seen[node]=1;
    for(i=0;i<dim;i++)
        if(seen[g[node][i]]==0)
            dfs(g[node][i]);
    cnt++;
    order[cnt]=node;
}
void anti_dfs(int node){
    int i,dim=gt[node].size();
    seen[node]=1;
    components[comp].push_back(node);
    for(i=0;i<dim;i++)
        if(seen[gt[node][i]]==0)
            anti_dfs(gt[node][i]);


}
int main(int node){
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m,a,b,i,dim,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d",&a,&b);
        g[a].push_back(b);
        gt[b].push_back(a);
    }
    cnt=comp=0;
    for(i=1;i<=n;i++)
        if(seen[i]==0)
            dfs(i);
    memset(seen,0,sizeof(seen));
    for(i=n;i>=1;i--)
        if(seen[order[i]]==0){
            comp++;
            anti_dfs(order[i]);
        }
    printf("%d\n",comp);
    for(i=1;i<=comp;i++){
        dim=components[i].size();
        for(j=0;j<dim;j++){
            printf("%d",components[i][j]);
            if(j==dim-1)
                printf("\n");
            else
                printf(" ");
        }
    }
    return 0;
}