Cod sursa(job #2165617)

Utilizator catalinlupCatalin Lupau catalinlup Data 13 martie 2018 12:52:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>
#define INFILE "ctc.in"
#define OUTFILE "ctc.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);

struct Graph{
    vector<vector<int>> Adj;
    void Init(int n){
        Adj.resize(n+1);
    }
    void Add(int x,int y){
        Adj[x].push_back(y);
    }
};
Graph G;
Graph Gt;
int N,M;
void Read(){
    in>>N>>M;
    G.Init(N);
    Gt.Init(N+1);
    for(int i=1;i<=M;i++){
        int x,y;
        in>>x>>y;
        G.Add(x,y);
        Gt.Add(y,x);
    }
}

void DFS(int x,vector<int>& noduri,bool viz[]){
    viz[x]=true;
    for(auto y:G.Adj[x]){
        if(viz[y]) continue;
        DFS(y,noduri,viz);
    }
    noduri.push_back(x);
}

void DFST(int x,bool viz[],vector<int>& componente){
    viz[x]=true;
    componente.push_back(x);
    for(auto y:Gt.Adj[x]){
        if(viz[y]) continue;
        DFST(y,viz,componente);
    }
}

void KosarjuSharir(){
    bool viz[N+1];
    vector<int> noduri;
    vector<vector<int>> componente;
    memset(viz,false,sizeof(viz));
    for(int i=1;i<=N;i++){
        if(!viz[i])
            DFS(i,noduri,viz);
    }
    memset(viz,false,sizeof(viz));
    while(!noduri.empty()){
        int x=noduri.back();
        noduri.pop_back();
        if(viz[x]) continue;
        vector<int> v;
        DFST(x,viz,v);
        componente.push_back(v);
    }
    out<<componente.size()<<"\n";
    for(auto v:componente){
        for(auto e:v){
            out<<e<<" ";
        }
        out<<"\n";
    }
}

int main(){
    Read();
    KosarjuSharir();
    return 0;
}