Cod sursa(job #1232345)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 22 septembrie 2014 18:50:25
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define NMAX 100007

using namespace std;

int Viz[NMAX], Ans[NMAX], Nr;
vector < int > v[NMAX], b[NMAX], Sol[NMAX];
int n, m;

void dfs(int Nod){
    Viz[Nod] = 1;
    for(int i = 0; i < v[Nod].size(); ++i)
        if(Viz[v[Nod][i]] == 0)
            dfs(v[Nod][i]);
    Ans[++Ans[0]] = Nod;
}

void dfs2(int Nod){
    Viz[Nod] = 1;
    Sol[Nr].push_back(Nod);
    for(int i = 0; i < b[Nod].size(); ++i)
        if(Viz[b[Nod][i]] == 0)
            dfs2(b[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){
        int x, y;
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        b[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i)
        if(Viz[i] == 0)
            dfs(i);
    for(int i = 1; i <= n; ++i)
        Viz[i] = 0;
    for(int i = n; i >= 1; --i)
        if(Viz[Ans[i]] == 0){
            ++Nr;
            dfs2(Ans[i]);
        }
    printf("%d\n", Nr);
    for(int i = 1; i <= Nr; ++i, printf("\n")){
        sort(Sol[i].begin(), Sol[i].end());
        for(int j = 0; j < Sol[i].size(); ++j)
            printf("%d ", Sol[i][j]);
    }
    return 0;
}