Cod sursa(job #1851822)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 20 ianuarie 2017 09:39:44
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> v[100010], con;
stack<int> stiva;
bitset<100010> in_stiva;
vector< vector<int> > sol;
int st[100010], dr[100010];
void df(int);
int n,m,x,y,pas;

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
        if(st[i]==0)
            df(i);
    int sz_sol = sol.size(), sx;
    fout<<sz_sol<<'\n';
    for(int i = 0; i< sz_sol; i++)
    {
        sx = sol[i].size();
        for(int j=0; j<sx; j++)
            fout<<sol[i][j]<<" ";
        fout<<'\n';
    }
    return 0;
}

void df(int nod)
{
    pas++;
    st[nod] = dr[nod] = pas;
    stiva.push(nod);
    in_stiva[nod]=1;
    for(auto it:v[nod])
    {
        if(st[it]==0)
        {
            df(it);
            dr[nod] = min(dr[nod], dr[it]);
        }
        else
            if(in_stiva[it] == 1)
                dr[nod] = min(dr[nod], dr[it]);
    }
    if(st[nod] == dr[nod])
    {
        con.clear();
        int t=stiva.top();
        while(t!=nod)
        {
            con.push_back(t);
            in_stiva[t] = 0;
            stiva.pop();
            t = stiva.top();
        }
        con.push_back(t);
        in_stiva[t] = 0;
        stiva.pop();
        sol.push_back(con);
    }




}