Cod sursa(job #903567)

Utilizator costyv87Vlad Costin costyv87 Data 1 martie 2013 22:30:49
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
//HighFlow
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <fstream>
#include <string.h>
#include <stack>
#include <cmath>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=st;i<=dr;i+=k)
#define ll (long long)
using namespace std;
FILE *f,*g;
stack < pair<int,int> > S;
vector <int> a[100100];
int ind[100100],mn[100100];
vector < vector<int> > sol;
int bf[100100];
vector <int> con;
int n,m,nv,ans;

void read()
{
    int i,x,y;

    f=fopen("biconex.in","r");
    g=fopen("biconex.out","w");

    fscanf(f,"%d%d",&n,&m);

    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        a[x].push_back(y);
        a[y].push_back(x);
    }

}

void ins(int x,int t)
{
    if (bf[x]==t) return;
    bf[x]=t; con.push_back(x);
}

void df(int x, int t)
{
    int i;
    mn[x]=ind[x]=++nv;

    for (i=0;i<a[x].size();i++)
    {
        if (a[x][i]==t) continue;
        if (ind[a[x][i]]!=0)
            mn[x]=min(mn[x],mn[a[x][i]]);
        else
        {
             S.push(make_pair(x,a[x][i]));
            df(a[x][i],x);
            mn[x]=min(mn[x],mn[a[x][i]]);
            ans++;
            if (mn[a[x][i]]>=ind[x])
            {
                int X,Y;
                con.clear();
                do
                {
                    X=S.top().first; Y=S.top().second;
                    S.pop();
                    ins(X,ans);  ins(Y,ans);
                }
                while (X!=x || Y!=a[x][i]);
                sol.push_back(con);
            }
        }

    }

}


void write()
{
    int i,j;

    fprintf(g,"%d\n",sol.size());

    for (i=0;i<sol.size();i++,fprintf(g,"\n"))
        for (j=0;j<sol[i].size();j++)
            fprintf(g,"%d ",sol[i][j]);
}

int main()
{

    read();
    df(1,0);
    write();
	return 0;
}