Cod sursa(job #2120950)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 3 februarie 2018 10:12:12
Problema Componente tare conexe Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
vector <int>  G[100005];
vector <int>  SOL[100005];
stack <int> s;
int m,n,solsize;
struct
{
    int index=0,lowlink=0,isInStack=0;
} v[100005];
void citire()
{
    scanf("%d%d",&n,&m);
    int aux1,aux2;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&aux1,&aux2);
        G[aux1].push_back(aux2);
    }
}
int idx=1;
void tarjan(int nod)
{
    s.push(nod);
    v[nod].index=idx++;
    v[nod].lowlink=v[nod].index;
    v[nod].isInStack=1;
    for(auto it:G[nod])
    {
        if(v[it].index==0)
        {
            tarjan(it);
            v[nod].lowlink=min(v[nod].lowlink,v[it].lowlink);
        }
        else
        {
            if(v[it].isInStack)
            {
                v[nod].lowlink=min(v[nod].lowlink,v[it].index);
            }
        }
    }
    if(v[nod].index==v[nod].lowlink)
    {
        while(s.top()!=nod&&!s.empty())
        {
            SOL[solsize].push_back(s.top());
            v[s.top()].isInStack=0;
            s.pop();
        }
        SOL[solsize].push_back(nod);
        solsize++;
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    citire();
    for(int i=1;i<=n;i++)
        if(v[i].index==0)
            tarjan(i);
    printf("%d\n",solsize);
    for(int i=0;i<solsize;i++)
    {
        for(auto ii:SOL[i])
            printf("%d ",ii);
        printf("\n");
    }
    return 0;
}