Cod sursa(job #2199836)

Utilizator unknownpersonBidasca Carina Georgiana unknownperson Data 29 aprilie 2018 11:55:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int N = 100010;
int n,m,i,x,y,k,A[N],B[N];
vector<int> v[N];
bool used[N];
void DF(int);
vector<int> c;
vector<vector<int>> C;
stack<int> st;
int main()
{
    f>>n>>m;
    for(; m; m--)
    {
        f>>x>>y;
        v[x].push_back(y);
    }
    for(i=1; i<=n; i++)
        if(!used[i])
            DF(i);
    g<<C.size()<<'\n';
    for(auto com:C)
    {
        for(auto it:com)
            g<<it<<' ';
        g<<'\n';
    }
            return 0;
}
void DF(int nod)
{
    A[nod]=B[nod]=++k;
    st.push(nod);
    for(auto vec:v[nod])
        if(!used[vec])
        {
            if(!A[vec])
                DF(vec);
            B[nod]=min(B[nod],B[vec]);
        }
    if(A[nod]==B[nod])
    {
        c.resize(0);
        do
        {
            x=st.top();used[x]=true;
            st.pop();
            c.push_back(x);
        }
        while(x!=nod);
        C.push_back(c);
    }
}