Cod sursa(job #2366914)

Utilizator EdgeLordXDOvidiuPita EdgeLordXD Data 4 martie 2019 22:55:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<int>a[N], b[N], r[N];
stack<int> st;
bool v[N];
int k=0;
void dfs(int i){
    v[i]=1;
    for(auto it:a[i])
        if(!v[it])
            dfs(it);
    st.push(i);
}
void dfsr(int i){
    v[i]=0;
    r[k].push_back(i);
    for(auto it:b[i])
        if(v[it])
            dfsr(it);
}
int main(){
    int n,m,i,x,y;
    in>>n>>m;
    for(i=1; i<=m; ++i){
        in>>x>>y;
        a[x].push_back(y);
        b[y].push_back(x);
    }
    for(i=1; i<=n ;++i)
        if(!v[i])
            dfs(i);
    while(!st.empty()){
        ++k;
        dfsr(st.top());
        while(!st.empty() && !v[st.top()])
            st.pop();
    }
    out<<k<<"\n";
    for(i=1; i<=k; ++i){
        for(auto it:r[i])
            out<<it<<" ";
        out<<"\n";
    }
    return 0;
}