Cod sursa(job #1900794)

Utilizator LucianTLucian Trepteanu LucianT Data 3 martie 2017 16:32:50
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include <bits/stdc++.h>
#define maxN 100005
using namespace std;
vector<int> v[maxN];
bool seen[maxN];
int stk[maxN],top;
int idx[maxN],low[maxN]; /* tarjan's algorithm */
int n,m,i,j,x,y,level;
vector<vector<int> >ctc;
vector<int> aux;
void tarjan(int nod) /* dfs */
{
    idx[nod]=low[nod]=++level;
    low[nod]=level; /* smallest reachable idx */

    stk[++top]=nod;
    seen[nod]=true;
    for(auto it:v[nod])
        if(!idx[it]){
            tarjan(it);
            low[nod]=min(low[nod],low[it]);
        }
        else if(seen[it])
            low[nod]=min(low[nod],idx[it]);
    if(idx[nod]==low[nod])
    {
        int newn;
        aux.clear();
        do /* popping nodes in scc */
        {
            newn=stk[top--];
            seen[newn]=false;
            aux.push_back(newn);
        }while(newn!=nod);
        ctc.push_back(aux);
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d %d",&x,&y),
        v[x].push_back(y);
    for(i=1;i<=n;i++)
        if(!idx[i])
            tarjan(i);
    printf("%d\n",ctc.size()); /* printing components */
    for(auto it:ctc)
    {
        for(auto nod:it)
            printf("%d ",nod);
        printf("\n");
    }
    return 0;
}