Cod sursa(job #2367336)

Utilizator PopeangaMihneaPopeanga Mihnea- Stefan PopeangaMihnea Data 5 martie 2019 10:14:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, timp, comp;
bool in_stack[100001];
int disc[100001], low[100001];
vector<int>G[100001], sol[100001];
stack<int>ST;

void DFS(int nod)
{
    in_stack[nod]=1;
    ST.push(nod);
    disc[nod]=low[nod]=++timp;
    for(auto it:G[nod])
    {
        if(!disc[it])
        {
            DFS(it);
            low[nod]=min(low[nod], low[it]);
        }
        else if(in_stack[it]) low[nod]=min(low[nod], disc[it]);
    }
    if(low[nod]==disc[nod])
    {
        ++comp;
        while(ST.top()!=nod)
        {
            in_stack[ST.top()]=0;
            sol[comp].push_back(ST.top());
            ST.pop();
        }
        in_stack[ST.top()]=0;
        sol[comp].push_back(ST.top());
        ST.pop();
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        int x, y;
        fin>>x>>y;
        G[x].push_back(y);
    }
    for(int i=1; i<=n; ++i) if(!disc[i]) DFS(i);
    fout<<comp<<"\n";
    for(int i=1; i<=comp; ++i)
    {
        sort(sol[i].begin(), sol[i].end());
        for(auto it:sol[i]) fout<<it<<" ";
        fout<<"\n";
    }
    return 0;
}