Cod sursa(job #2046004)

Utilizator Tataru_AdelinTataru Adelin Tataru_Adelin Data 23 octombrie 2017 11:35:10
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N = 100010;
int n,m,x,y,nr,a[N],b[N];
vector<int> v[N],c;
vector<vector<int>> C;
stack<int> S;
bitset<N> s;
void df(int);
int main()
{
    f>>n>>m;
    for(;m;m--)
    {
        f>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        if(!a[i])
            df(i);
    g<<C.size();
    for(auto comp : C)
    {
        for(auto it:comp)
            g<<it<<' ';
        g<<'\n';
    }
    return 0;
}
void df(int nod)
{
    a[nod]=b[nod]=++nr;
    S.push(nod);
    s[nod]=1;
    for(auto vec:v[nod])
        if(!a[vec])
        {
            df(vec);
            b[nod]=min(b[nod],b[vec]);
        }
        else
        if(s[vec])
           b[nod]=min(b[nod],b[vec]);
    if(a[nod]!=b[nod])return;
    c.resize(0);
    for(;;)
    {
        x=S.top();
        S.pop();
        s[x]=0;
        c.push_back(x);
        if(x==nod)break;
    }
}