Cod sursa(job #2133346)

Utilizator tudor199G Tudor tudor199 Data 16 februarie 2018 20:21:13
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 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] = {};
vector < int > v[nMax], rv[nMax];
pair < int, int > idx[nMax];
vector < vector < int > > sol;
vector < int > x;

auto cmp = [](pair < int, int > a, pair < int, int > b){return a.first < b.first;};
priority_queue < pair < int, int > , vector < pair< int, int > >, decltype(cmp) > heap(cmp);

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]);
        }
    }
    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 = 1; i <= n; i ++){
        heap.push(make_pair(idx[i]._2, i));
    }
    while(!heap.empty()){
        now = heap.top();
        heap.pop();
        if(partof[now.second]){
            continue;
        }
        sol.resize(sol.size() + 1);
        r_dfs(now.second);
    }
    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;
}