Pagini recente » Cod sursa (job #123051) | Cod sursa (job #484775) | Cod sursa (job #1770536) | Cod sursa (job #1301328) | Cod sursa (job #500857)
Cod sursa(job #500857)
#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;
}