Cod sursa(job #2232043)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 17 august 2018 07:46:21
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define MAXN 100005

using namespace std;

ifstream in("cct.in");
ofstream out("cct.out");

vector<int>graf[MAXN],graf_transpus[MAXN],ans[MAXN];
queue<int>discovered;
bool viz[MAXN];
int n,m,cnt;

void init(){
    for(int i = 0; i < MAXN; i++)
        viz[i] = false;
}
void dfs1(int start){
    viz[start] = true;
    int curent;
    for(int i = 0; i < graf[start].size(); i++){
        curent = graf[start][i];
        if(!viz[curent])
            dfs1(curent);

    }
    discovered.push(start);
}

void dfs2(int start){
    viz[start] = true;

    int curent;
    ans[cnt].push_back(start);
    for(int i = 0; i < graf[start].size(); i++){
        curent = graf[start][i];
        if(!viz[curent])
            dfs2(curent);
    }

}


int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; i++){
        int nod,muchie;
        in>>nod>>muchie;
        graf[nod].push_back(muchie);
        graf_transpus[muchie].push_back(nod);
    }

    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs1(i);
    init();

    while(discovered.size()){
        int nod = discovered.front();
        discovered.pop();
        if(!viz[nod]){
            dfs2(nod);
            cnt++;
        }
    }
    out<<cnt<<"\n";

    for(int i = 0; i < cnt; i++){
        for(int j = 0; j < ans[i].size(); j++)
            out<<ans[i][j]<<" ";
        out<<"\n";
    }
    return 0;
}