Cod sursa(job #1252776)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 31 octombrie 2014 11:33:49
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
vector<int> a[100005], b[100005], g[100005];
vector<int>::iterator it;
int i, n, m, st[100005], sol, x, y;
bool u[100005];
void dfs1(int poz){
    vector<int>::iterator it;
    u[poz]=true;
    for (it=a[poz].begin();it!=a[poz].end();it++) if (u[*it]==false)
        dfs1(*it);
    st[++st[0]]=poz;
}
void dfs2(int poz){
    vector<int>::iterator it;
    u[poz]=true; g[sol].push_back(poz);
    for (it=b[poz].begin();it!=b[poz].end();it++) if (u[*it]==false)
        dfs2(*it);
}
int main(){
    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); a[x].push_back(y); b[y].push_back(x);
    }
    memset(u, 0, sizeof(u)); memset(st, 0, sizeof(st));
    for (i=1;i<=n;i++) if (u[i]==false) dfs1(i);
    memset(u, 0, sizeof(u));
    for (i=n;i>=1;i--) if (u[st[i]]==false) {
        sol++; dfs2(st[i]);
    }
    printf("%d\n", sol);
    for (i=1;i<=sol;i++) {
        for (it=g[i].begin();it!=g[i].end();it++) printf("%d ", *it);
        printf("\n");
    }
    return 0;
}