Cod sursa(job #2133186)

Utilizator tudor199G Tudor tudor199 Data 16 februarie 2018 17:23:02
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

#define _1 first
#define _2 second

#define nMax 100003

using namespace std;

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

int n, m, index = 0;
bool partof[nMax] = {};
int order[nMax], n_order = 0;
vector < int > v[nMax], rv[nMax];
pair < int, int > idx[nMax];
vector < vector < int > > sol;
vector < int > x;

void r_dfs(int nod){
    partof[nod] = true;
    sol[sol.size() - 1].push_back(nod);
    for(int i = 0; i < rv[nod].size(); i ++){
        if(!partof[rv[nod][i]]){
            r_dfs(rv[nod][i]);
        }
    }
    return;
}

void dfs(int nod){
    idx[nod]._1 = ++ index;
    for(int i = 0; i < v[nod].size(); i ++){
        if(!idx[v[nod][i]]._1){
            dfs(v[nod][i]);
        }
    }
    order[++ n_order] = nod;
    idx[nod]._2 = ++ index;
    return;
}

void tarjan(){
    pair < int, int > now;
    for(int i = 1; i <= n; i ++){
        if(!idx[i]._1){
            dfs(i);
        }
    }
    for(int i = n, now; i > 0; i --){
        now = order[i];
        if(partof[now]){
            continue;
        }
        sol.resize(sol.size() + 1);
        r_dfs(now);
    }
    return;
}

int main(){
    int m;
    fin>>n>>m;
    for(int i = 1, x, y; i <= m; i ++){
        fin>>x>>y;
        v[x].push_back(y);
        rv[y].push_back(x);
    }
    tarjan();
    fout<<sol.size()<<"\n";
    for(int i = 0; i < sol.size(); i ++){
        for(int j = 0; j < sol[i].size(); j ++){
            fout<<sol[i][j]<<" ";
        }
        fout<<"\n";
    }
	return 0;
}