Pagini recente » Cod sursa (job #2565155) | Cod sursa (job #2471380) | Cod sursa (job #155974) | Cod sursa (job #524852) | Cod sursa (job #903567)
Cod sursa(job #903567)
//HighFlow
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <fstream>
#include <string.h>
#include <stack>
#include <cmath>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=st;i<=dr;i+=k)
#define ll (long long)
using namespace std;
FILE *f,*g;
stack < pair<int,int> > S;
vector <int> a[100100];
int ind[100100],mn[100100];
vector < vector<int> > sol;
int bf[100100];
vector <int> con;
int n,m,nv,ans;
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);
}
}
void ins(int x,int t)
{
if (bf[x]==t) return;
bf[x]=t; con.push_back(x);
}
void df(int x, int t)
{
int i;
mn[x]=ind[x]=++nv;
for (i=0;i<a[x].size();i++)
{
if (a[x][i]==t) continue;
if (ind[a[x][i]]!=0)
mn[x]=min(mn[x],mn[a[x][i]]);
else
{
S.push(make_pair(x,a[x][i]));
df(a[x][i],x);
mn[x]=min(mn[x],mn[a[x][i]]);
ans++;
if (mn[a[x][i]]>=ind[x])
{
int X,Y;
con.clear();
do
{
X=S.top().first; Y=S.top().second;
S.pop();
ins(X,ans); ins(Y,ans);
}
while (X!=x || Y!=a[x][i]);
sol.push_back(con);
}
}
}
}
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();
df(1,0);
write();
return 0;
}