Cod sursa(job #2279471)

Utilizator AlexTheDagonBogdan Tudor AlexTheDagon Data 9 noiembrie 2018 16:48:20
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define pb push_back
#define NM 100005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");

vector<int> G[NM],GT[NM];

vector<int> sol[NM];
stack<int> st;

int n,m,a,b,nrs;
int viz[NM];

void dfs(int nod)
{
    viz[nod]=1;
    for(auto fiu:G[nod])
        if(!viz[fiu])
            dfs(fiu);
    st.push(nod);
}

void dfst(int nod)
{
    viz[nod]=1;
    sol[nrs].pb(nod);
    for(auto fiu:GT[nod])
        if(!viz[fiu])
            dfst(fiu);
}



int main()
{
    in>>n>>m;
    for(int i=1;i<=m;++i)
    {
        in>>a>>b;
        G[a].pb(b);
        GT[b].pb(a);
    }
    for(int i=1;i<=n;++i)
        if(!viz[i])
            dfs(i);
    for(int i=1;i<=n;++i)
        viz[i]=0;
    while(!st.empty())
    {
        while(!st.empty() && viz[st.top()])st.pop();
        if(!st.empty())
        {
            ++nrs;
            dfst(st.top());
            st.pop();
        }
    }
    out<<nrs<<'\n';
    for(int i=1;i<=nrs;++i)
    {
        for(auto nod:sol[i])out<<nod<<" ";
        out<<'\n';
    }
    return 0;
}