Cod sursa(job #2120949)

Utilizator maria_sinteaMaria Sintea maria_sintea Data 3 februarie 2018 10:12:09
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#define min(a, b) a<b?a:b
#define N 100005

using namespace std;

vector <int> graf[N], sol[N];
stack <int> s;
vector <int> :: iterator it;
int viz[N], n, m, nr, index[N], lowlink[N], ind=1;

void citire()
{
    scanf("%d %d\n", &n, &m);
    for(int i=0;i<m;i++)
    {
        int x, y;
        scanf("%d %d\n", &x, &y);
        graf[x].push_back(y);
    }
}

void afisare()
{
    printf("%d\n", nr);
    for(int i=1;i<=nr;i++)
    {
        for(int j=0;j<sol[i].size();j++)
            printf("%d ", sol[i][j]);
        printf("\n");
    }
}

void dfs(int x)
{
    index[x]=lowlink[x]=++ind;
    s.push(x);
    viz[x]=1;
    for(int i=0;i<graf[x].size();i++)
    {
        int nod=graf[x][i];
        if(!index[nod])
        {
            dfs(nod);
            lowlink[x]=min(lowlink[x], lowlink[nod]);
        }
        else
            if(viz[nod])
                lowlink[x]=min(lowlink[x], index[nod]);
    }

    if(lowlink[x]==index[x])
    {
        nr++;
        int y;
        do {
          y = s.top();
          sol[nr].push_back(y);
          s.pop();
          viz[y] = 0;
        } while(y != x);
    }
}

void tarjan()
{
    for(int i=1;i<=n;i++)
        if(!index[i])
            dfs(i);
}

int main()
{
    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);

    citire();
    tarjan();
    afisare();
    return 0;
}