Cod sursa(job #1455853)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 29 iunie 2015 11:49:51
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>

#define NMAX 100007

using namespace std;

vector < int > v[NMAX], V[NMAX], Sol[NMAX];
bool Viz[NMAX];
int Ans[NMAX];
int n, m, NrSol;

void dfs(int Nod){
    Viz[Nod] = 1;
    for(vector < int >::iterator it = v[Nod].begin(); it != v[Nod].end(); ++it)
        if(Viz[*it] == 0)
            dfs(*it);
    Ans[++Ans[0]] = Nod;
}

void dfs2(int Nod){
    Viz[Nod] = 1;
    Sol[NrSol].push_back(Nod);
    for(vector < int >::iterator it = V[Nod].begin(); it != V[Nod].end(); ++it)
        if(Viz[*it] == 0)
            dfs2(*it);
}

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);
        V[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i)
        if(Viz[i] == 0)
            dfs(i);
    memset(Viz, 0, sizeof(Viz));
    for(int i = n; i >= 1; --i)
        if(Viz[Ans[i]] == 0){
            ++NrSol;
            dfs2(Ans[i]);
        }
    printf("%d\n", NrSol);
    for(int i = 1; i <= NrSol; ++i){
        sort(Sol[i].begin(), Sol[i].end());
        for(vector < int >::iterator it = Sol[i].begin(); it != Sol[i].end(); ++it)
            printf("%d ", *it);
        printf("\n");
    }
    return 0;
}