Cod sursa(job #1686841)

Utilizator gabib97Gabriel Boroghina gabib97 Data 12 aprilie 2016 14:33:34
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
int n,m,i,niv[100001],low[100001],nr,j;
bool o[100001];
vector<int> G[100001],r[100001];
stack<pair<int,int> > S;
void citire()
{
    int i,x,y;
    scanf("%i%i",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%i%i",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
void afis(int t,int s)
{
    int a,b;
    pair<int,int> p;
    nr++;
    r[nr].push_back(t);
    do
    {
        p=S.top();
        S.pop();
        a=p.first;
        b=p.second;
        r[nr].push_back(b);
    }while (a!=t||b!=s);
}
void DFS(int s,int t)  //s - nodul curent, t - tatal nodului s
{
    int i,z=G[s].size(),x;
    o[s]=1;
    low[s]=niv[s];
    for (i=0;i<z;i++)
    {
        x=G[s][i];
        if (!o[x])
        {
            S.push(make_pair(s,x)); //inseram muchia in stiva
            niv[x]=niv[s]+1;
            DFS(x,s);
            low[s]=min(low[s],low[x]); //actualizez low[s]

            if (low[x]>=niv[s]) afis(s,x); //s este punct de articulatie, deci am mai gasit o comp. biconexa
        }
        else if (x!=t) low[s]=min(low[s],low[x]);
    }
}
int main()
{
    freopen ("biconex.in","r",stdin);
    freopen ("biconex.out","w",stdout);
    citire();
    for (i=1;i<=n;i++)
        if (!o[i]) DFS(i,-1);
    printf("%i",nr);
    for (i=1;i<=nr;i++)
    {
        printf("\n");
        for (j=0;j<r[i].size();j++) printf("%i ",r[i][j]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}