Cod sursa(job #2436922)

Utilizator vladth11Vlad Haivas vladth11 Data 7 iulie 2019 17:28:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int n,m;
int nrctc;
vector <int> ctc[100001];
vector <int> v[100001];
vector <int> inv[100001];
int viz[100001];
stack <int> stiva;
void DFS(int nod){
    viz[nod] = 1;
    for(int i = 0;i < v[nod].size();i++){
        int vecin = v[nod][i];
        if(!viz[vecin]){
            DFS(vecin);
        }
    }
    stiva.push(nod);
}
void DFS2(int nod){
    viz[nod] = 2;
    ctc[nrctc].push_back(nod);
    for(int i = 0;i < inv[nod].size();i++){
        int vecin = inv[nod][i];
        if(viz[vecin] == 1){
            DFS2(vecin);
        }
    }
    
}
int main() {
    int i;
    in >> n >> m;
    for(i = 1;i <= m;i++){
        int x,y;
        in >> x >> y;
        v[x].push_back(y);
        inv[y].push_back(x);
    }
    for(i = 1;i<= n;i++){
        if(!viz[i]){
            DFS(i);
        }
    }
    while(!stiva.empty()){
        int nod = stiva.top();
        
        if(viz[nod] == 1)
        nrctc++,DFS2(nod);
        stiva.pop();
    }
    out << nrctc << "\n";
    for(i = 1;i <= nrctc;i++){
        for(int j = 0;j < ctc[i].size();j++){
            out << ctc[i][j] << " ";
        }
        out << "\n";
    }
    return 0;
}