Cod sursa(job #2171185)

Utilizator calin1Serban Calin calin1 Data 15 martie 2018 11:30:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#include <bitset>
#define N 100005

using namespace std;

int n, m, index[N], lowlink[N], global_index, nr;

vector <int> G[N], componente[N];

bitset <N> viz, in_stack;

stack <int> S;

void dfs(int nod)
{
    viz[nod] = true;

    index[nod] = ++global_index;

    lowlink[nod] = index[nod];

    S.push(nod);

    in_stack[nod] = true;

    vector <int>::iterator it;

    for(it = G[nod].begin() ; it != G[nod].end() ; ++it)
    {
        if(!viz[*it])
        {
            dfs(*it);

            lowlink[nod] = min(lowlink[nod] , lowlink[*it]);
        }
        else
        {
            if(in_stack[*it])
            {
                lowlink[nod] = min(lowlink[nod] , lowlink[*it]);
            }
        }
    }

    if(lowlink[nod] == index[nod])
    {
        int x;

        do
        {
            x = S.top();

            S.pop();

            in_stack[x] = false;

            componente[nr].push_back(x);

        }while(x != nod);

        nr++;
    }
}

void afisare()
{
    printf("%d\n", nr);

    for(int i = 0 ; i < nr ; ++i)
    {
        for(int j = 0 ; j < componente[i].size() ; ++j)
        {
            printf("%d ", componente[i][j]);
        }

        printf("\n");
    }
}

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

    afisare();
}

void citire()
{
    scanf("%d %d\n", &n, &m);

    int x, y;

    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d\n", &x, &y);

        G[x].push_back(y);
    }

    prelucrare();
}

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

    citire();

    return 0;
}