Cod sursa(job #499245)

Utilizator marius21Marius Petcu marius21 Data 9 noiembrie 2010 11:57:17
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <cstdio>
#include <cstdlib>
#include <list>
#include <vector>
using namespace std;

FILE *fin=fopen("biconex.in","r");
FILE *fout=fopen("biconex.out","w");

vector<int> v[100001];
int lvl[100001];
list<int> stk;
list< list<int> > res;

void df(int n, int ln, int lv)
{
    lvl[n]=lv;
    stk.push_back(n);
    for (vector<int>::iterator i=v[n].begin(); i!=v[n].end(); i++)
    {
        int ch = *i;
        if (ch==ln) continue;
        if ((lvl[ch])&&(lvl[ch]<lv))
        {
            list<int> r;
            while (stk.back()!=ch)
            {
                r.push_front(stk.back());
                stk.pop_back();
            }
            r.push_front(ch);
            res.push_back(r);
        }
        if (!lvl[ch])
            df(ch,n,lv+1);
    }
    if (stk.back()==n)
    {
        stk.pop_back();
        if (ln!=0)
        {
            list<int> r;
            r.push_back(ln);
            r.push_back(n);
            res.push_back(r);
        }
    }
}

void read_in()
{
    FILE * fin = fopen("biconex.in","r");
    int n,m;
	fscanf(fin,"%d%d",&n,&m);
	for (int i=0; i<m ; i++)
	{
		int x,y;
		fscanf(fin,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
	}
    fclose(fin);
}

void write_out()
{
    FILE * fout = fopen("biconex.out","w");
    fprintf(fout,"%d\n",(int)res.size());
    for (std::list< list<int> >::iterator i=res.begin(); i!=res.end(); i++)
    {
        for (std::list<int>::iterator j=(*i).begin(); j!=(*i).end(); j++)
            fprintf(fout,"%d ",(*j));
        fputc('\n',fout);
    } 
    fclose(fout);
}

int main (int argc, char * const argv[]) {
	read_in();
    df(1,0,1);
    write_out();
    return 0;
}