Cod sursa(job #2187341)

Utilizator VladG26Ene Vlad-Mihai VladG26 Data 26 martie 2018 13:41:14
Problema Componente tare conexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#include <vector>
#include <stack>
#define NMAX 100005
using namespace std;
int m,n,cnt;
vector<int> G[NMAX],comp[NMAX];
stack<int> tarjan;
int viz[NMAX],inStack[NMAX],niv[NMAX],best[NMAX];
void insetNod(int nod)
{
    comp[cnt].push_back(nod);
    inStack[nod]=0;
    tarjan.pop();
}
void solve(int nod,int tata)
{
    inStack[nod]=viz[nod]=1;
    tarjan.push(nod);
    niv[nod]=best[nod]=niv[tata]+1;
    for(auto fiu:G[nod])
    {
        if(!viz[fiu])
        {
            solve(fiu,nod);
            best[nod]=min(best[nod],best[fiu]);
        }
        else if(inStack[fiu])
            best[nod]=min(best[nod],best[fiu]);
    }
    if(best[nod]==niv[nod])
    {
        cnt++;
        while(tarjan.top()!=nod)
        {
            insetNod(tarjan.top());
        }
        insetNod(tarjan.top());
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    int nod1,nod2;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&nod1,&nod2);
        G[nod1].push_back(nod2);
    }
    for(int i=1;i<=n;i++)
        if(!viz[i])
            solve(i,0);
    printf("%d\n",cnt);
    for(int i=1;i<=cnt;i++)
    {
        for(auto nod:comp[i])
            printf("%d ",nod);
        printf("\n");
    }
    return 0;
}