Cod sursa(job #937137)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 9 aprilie 2013 22:20:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.81 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int NMAX = 100005;
int n,m,x,y,i,j,cnt,N;
int Dft[NMAX]; // Dft[x] = numarul de ordine al nodului x dupa parcurgerea DFS
int Low[NMAX]; // Low[x] = numarul de ordine al primului nod ce poate fi atins din x pe alt drum decat cel din parcurgerea DFS
vector<int> V[NMAX],Sol[NMAX];
vector<pair<int,int> > St;
void Get_Sol(int A,int B)
{
    int X,Y;
    vector<pair<int,int> >::iterator it; N++;
    do
    {
        it=St.end(); it--;
        X=it->first;
        Y=it->second;
        St.pop_back();
        Sol[N].push_back(Y);
    }
    while(X!=A || Y!=B);
    Sol[N].push_back(X);
}
void DFS(int Node,int Father)
{
    Dft[Node]=Low[Node]=++cnt;
    for(vector<int>::iterator it=V[Node].begin();it!=V[Node].end();it++)
    {
        if(*it==Father) continue;
        if(!Dft[*it])
        {
            St.push_back(make_pair(Node,*it));
            DFS(*it,Node);
            Low[Node]=min(Low[Node],Low[*it]);
            // actualizam Low pe baza fiilor

            if(Low[*it]>=Dft[Node]) Get_Sol(Node,*it);
            // am gasit un punct de articulatie
        }
        else Low[Node]=min(Low[Node],Dft[*it]);
        // am gasit o muchie de intoarcere si putem sa actualizam actualizam Low
    }
}
void Read()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d",&x,&y);
        V[x].push_back(y);
        V[y].push_back(x);
    }
    DFS(1,0);
}
void Print()
{
    printf("%d\n",N);
    for(i=1;i<=N;i++)
    {
        for(vector<int>::iterator it=Sol[i].begin();it!=Sol[i].end();it++) printf ("%d ",*it);
        printf("\n");
    }
}
int main()
{
    Read();
    Print();
    return 0;
}