Cod sursa(job #2128132)

Utilizator stefanchistefan chiper stefanchi Data 11 februarie 2018 14:41:56
Problema Componente tare conexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>

using namespace std;
const int NMAX = 100010;
vector <int> graf[NMAX];
int n,m,index[NMAX],lowlink[NMAX],valinitiala,componente;
stack <int> stiva;
vector<int> solutie[NMAX];
bitset <NMAX> inside;


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

void dfs(int nod)
{
    valinitiala++;
    index[nod] = lowlink[nod] = valinitiala;
    inside[nod] = true;
    stiva.push(nod);
    for(vector <int> :: iterator it = graf[nod].begin(); it!= graf[nod].end() ; it++)
    {
        if( index[*it] == 0)
        {
            dfs(*it);
            lowlink[nod] = min(lowlink[*it],lowlink[nod]);
        }
        else if(inside[*it] == true)
                lowlink[nod] =  min(lowlink[*it],lowlink[nod]);

    }

    if( lowlink[nod] == index[nod])
    {
        componente++;
        int auxnod= stiva.top();
        stiva.pop();
        inside[auxnod] = true;
        solutie[componente].push_back(auxnod);
        while(auxnod != nod)
        {
            auxnod = stiva.top();
            inside[auxnod] = true;
            solutie[componente].push_back(auxnod);
            stiva.pop();
        }

    }
}

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

int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    read();
    rezolvare();
    printf("%d\n",componente);
    for(int i = 1 ; i <= componente; i++)
    {
        for(vector <int> :: iterator it = solutie[i].begin( ); it != solutie[i].end() ; it++)
            printf("%d ",*it);
        printf("\n");
    }
    return 0;
}