Cod sursa(job #2232046)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 17 august 2018 08:05:16
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#define MAXN 100005

using namespace std;

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

vector<int>graf[MAXN],graf_transpus[MAXN],scc[MAXN];
stack<int>stiva;
bool viz[MAXN];
int n,m,cnt;


void dfs(int start){
    viz[start] = true;
    for(auto i : graf[start])
        if(!viz[i])
            dfs(i);
    stiva.push(start);
}

void dfs_reverse(int start){
    viz[start] = true;
    cout<<start<<" ";
    scc[cnt].push_back(start);
    for(auto i : graf_transpus[start])
        if(!viz[i])
            dfs_reverse(i);
}

void Kosaraju(){


    for(int i = 1; i <= n; i++)
        viz[i] = false;
    while(!stiva.empty()){
        int nod = stiva.top();
        stiva.pop();
        if(!viz[nod]){
            dfs_reverse(nod);
            cnt++;
        }
    }
}


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

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

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