Cod sursa(job #500857)

Utilizator costyv87Vlad Costin costyv87 Data 13 noiembrie 2010 13:06:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<stdio.h>
#include <vector>
#include <cstdio>
#include <utility>
#include <list>
FILE *f,*g;
using namespace std;
vector <int> v[100001];
int lvl[100001];
int mnm[100001];
int uni[100001];
list <pair <int,int> > stk;
vector < int> sol[10000];
int n,m,nn;

inline void ok(int n,int nr)
{
if (uni[n]!=nr) {
    uni[n]=nr;
    sol[nr].push_back(n);
    }
}

int df(int n,int ln,int lv) {
int mn=lvl[n]= lv;
stk.push_back(make_pair(ln,n));
for (int i=0;i<v[n].size();i++) {
    int ch=v[n][i];

    if (ch==ln) continue;

    if (lvl[ch] && (lvl[ch]<lv)) {
        mn=min(mn,lvl[ch]);
        }

    if (!lvl[ch]) {
        mn=min(df(ch,n,lv+1),mn);
        if (mnm[ch]>=lv)
            {
                int st,en;
                nn++;
                do
                {
                    ok(st = stk.back().first,nn);
                    ok(en = stk.back().second,nn);
                    stk.pop_back();
                } while (!((st==n)&&(en==ch)));
            }

        }
    }
    mnm[n]=mn;
    return mn;
}

void write() {
fprintf(g,"%d\n",nn);
for (int i=1;i<=nn;i++) {
    for (vector<int> ::iterator j=sol[i].begin(); j!=sol[i].end() ;j++)
     // for (int j=0;j<v[i].size() ;j++)
        fprintf(g,"%d ",*j);
    fprintf(g,"\n");
    }
fclose(g);
}

void read() {
int i,x,y;
fscanf(f,"%d%d",&n,&m);
for (i=1;i<=m;i++)  {
    fscanf(f,"%d %d",&x,&y);
    v[x].push_back(y);
    v[y].push_back(x);
    }
fclose(f);
}

int main () {
f=fopen("biconex.in","r");
g=fopen("biconex.out","w");
read();
df(1,0,1);
write();
return 0;
}