Cod sursa(job #2379472)

Utilizator onipreponiprep oniprep Data 13 martie 2019 17:55:24
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N=100009;
int n,m,nr,index;
int onsk[N],d[N],low[N];
vector <int> v[N],sol[N];
stack <int> sk;
void dfs(int nod)
{
    onsk[nod]=1;
    sk.push(nod);
    d[nod]=low[nod]=++index;
    for(int i=0;i<v[nod].size();i++)
        if(!d[v[nod][i]])
        {
            dfs(v[nod][i]);
            low[nod]=min(low[nod],low[v[nod][i]]);
        }
        else
            if(onsk[v[nod][i]])
                low[nod]=min(low[nod],low[v[nod][i]]);
    if(d[nod]==low[nod])
    {
        nr++;
        while(1)
        {
            int nodc=sk.top();
            onsk[nodc]=0;
            sk.pop();
            sol[nr].pb(nodc);
            if(nodc==nod)
                break;
        }
    }
}
void solve()
{
    for(int i=1;i<=n;i++)
        if(!d[i])
            dfs(i);
    fout<<nr<<'\n';
    for(int i=1;i<=nr;i++)
    {
        for(int j=0;j<sol[i].size();j++)
            fout<<sol[i][j]<<" ";
        fout<<'\n';
    }
}
int main()
{
    fin.sync_with_stdio(false);
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        v[x].pb(y);
    }
    solve();
    return 0;
}