Cod sursa(job #1993607)

Utilizator netfreeAndrei Muntean netfree Data 23 iunie 2017 13:05:59
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 100000+5;

vector<int> vec[N_MAX], rev_vec[N_MAX];
stack<int> q;

bitset<N_MAX> visited, visited2;

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

vector<int> temp;

vector<vector<int> > ans;

int n, m;

void dfs_q(int nod){

    visited[nod] = true;

    for(auto i : vec[nod])
        if(!visited[i])
            dfs_q(i);

    q.push(nod);

}

void dfs(int nod){
    temp.push_back(nod);
    visited2[nod] = true;

    for(auto i : rev_vec[nod])
        if(!visited2[i])
            dfs(i);
}

int main()
{
    fin >> n >> m;
    for(int i = 1,a,b; i<=m; ++i){
        fin >> a >> b;
        vec[a].push_back(b);
        rev_vec[b].push_back(a);
    }

    for(int i = 1; i<=n; ++i)
        if(!visited[i])
            dfs_q(i);

    while(!q.empty()){
        temp.clear();
        //cout << q.top() << endl;
        if(!visited2[q.top()])
            dfs(q.top());
        if(temp.size())
            ans.push_back(temp);
        q.pop();
    }

    fout << ans.size() << "\n";
    for(auto i : ans){
        for(auto j : i)
            fout << j << " ";
        fout << "\n";
    }

    return 0;
}