Cod sursa(job #1390513)

Utilizator sicsicFMI-Coteanu Vlad sicsic Data 17 martie 2015 08:57:05
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
bool U[100001],Stare[100001];
int T[100001],Dp[100001],Mn[100001],m,n,F[100001],X[100001];
struct lista{int nod; lista *leg;} *G[100001];
void adaug(int i,int j)
{
    lista *p;
    p=new lista;
    p->nod=j;
    p->leg=G[i];
    G[i]=p;
}
void citire()
{
    f>>n>>m;
    int i,j;
    while(m--)
    {
        f>>i>>j;
        adaug(i,j);
        adaug(j,i);
    }
}
void DFS(int s)
{
    lista *p;
    U[s]=1;
    Mn[s]=Dp[s];
    X[++X[0]]=s;
    for(p=G[s];p;p=p->leg)
        if(!U[p->nod])
        {
              F[s]++;
              Dp[p->nod]=Dp[s]+1;
              T[p->nod]=s;
              DFS(p->nod);
              Mn[s]=min(Mn[s],Mn[p->nod]);
        }
        else if(p->nod!=T[s]) Mn[s]=min(Dp[p->nod],Mn[s]);
    if(Dp[s]!=1) { if(Dp[T[s]]!=1&&Mn[s]>=Dp[T[s]]) { Stare[T[s]]=1; } }
    else if(F[s]>1) Stare[s]=1;
}
void Afis()
{
    for(int i=1;i<=X[0];++i)
    {
       // g<<X[i]<<" "<<Stare[X[i]]<<'\n';
        g<<X[i]<<" ";
        if(Stare[X[i]])
        {
            g<<'\n';
            g<<X[i]<<" ";
        }

    }
}
int main()
{
    citire();
    for(int i=1;i<=n;++i)
        if(!U[i])
        {
            Dp[i]=1;
            memset(X,0,sizeof X);
            DFS(i);
            Afis();
                g<<'\n';
        }
    return 0;
}