Cod sursa(job #718461)

Utilizator costyv87Vlad Costin costyv87 Data 20 martie 2012 20:21:26
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <cstdio>
#include <vector>
#include <stack>
#define nm 100100
using namespace std;
FILE *f,*g;

struct muchie {int x,y; } ax;
vector <int> a[nm],cn;
vector <vector <int> > sol;
stack <pair <int ,int > > S;
int lv[nm],mn[nm],bf[nm];

int n,m,i,lvl=0,nn=0;

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);
        }
}

inline int ins(int x,int y) {

if (bf[x]!=y) {
    bf[x]=y;
    cn.push_back(x);
    }

}

void df(int x,int t) {
int i,j,st,dr;

lv[x]=mn[x]=++lvl;

for (i=0;i<a[x].size();i++) {
        j=a[x][i];
        if (j==t) continue;

        if (lv[j] && lv[j]<lv[x])  mn[x]=min(mn[x],mn[j]);

        if (!lv[j]) {
            S.push(make_pair(x,j));
            df(j,x);
            mn[x]=min(mn[x],mn[j]);
            if (mn[j]>=lv[x]) {
                cn.clear();
                ++nn;
                do {
                        ins(st=S.top().first,nn);
                        ins(dr=S.top().second,nn);
                        S.pop();
                        }
                while ( !(st==x && dr==j)) ;
                sol.push_back(cn);
                }
            }

        }


}

void solve() {
lvl=1;
df(1,0);
}

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();
solve();
write();

return 0;
}