Cod sursa(job #862671)

Utilizator aladinaladin aladinn aladin Data 22 ianuarie 2013 20:37:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <cstdio>
#include <cstdlib>
#include <list>
#include <vector>
#include <utility>
using namespace std;
 
vector<int> v[100001];
int lvl[100001];
int mnm[100001];
list< pair<int,int> > stk;
vector< list<int>* > res;
int unq[100001];
 
inline void unique(int n, int nr, list<int> & r)
{
    if (unq[n]!=nr)
    {
        unq[n]=nr;
        r.push_back(n);
    }
}
 
int df(int n, int ln, int lv)
{
    int mn = lvl[n] = lv;
    stk.push_back(make_pair(ln,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))
        {
            mn=min(mn,lvl[ch]);
        }
        if (!lvl[ch])
        {
            mn=min(mn,df(ch,n,lv+1));
            if (mnm[ch]>=lv)
            {
                list<int> * r = new list<int>;
                int st,en;
                int nr = res.size()+1;
                do
                {
                    unique(st = stk.back().first,nr,*r);
                    unique(en = stk.back().second,nr,*r);
                    stk.pop_back();
                } while (!((st==n)&&(en==ch)));
                res.push_back(r);
            }
        }
    }
    mnm[n] = mn;
    //printf("nod: %d lvl:%d min:%d\n",n,lv,mn);
    return mn;
}
 
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 (vector< list<int>* >::iterator i=res.begin(); i!=res.end(); i++)
    {
        list<int> * el = *i;
        for (list<int>::iterator j=el->begin(); j!=el->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;
}