Pagini recente » Cod sursa (job #40763) | Cod sursa (job #2394929) | Cod sursa (job #370905) | Cod sursa (job #2034081) | Cod sursa (job #651124)
Cod sursa(job #651124)
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
FILE*f=fopen("biconex.in","r");
FILE*g=fopen("biconex.out","w");
int j,n,m,x,y,nr,niv1[100004],minniv[100004];
char viz[100001];
vector <int> v[100002];
vector <vector <int> > S;
struct stiva{
int x,y;
} stv[200002];
inline int min(int a,int b){
if(a<b)
return a;
return b;
}
void dfs(int nod,int father,int niv){
viz[nod]=1;
niv1[nod]=minniv[nod]=niv;
for(int i=0;i<v[nod].size();++i)
{
if(v[nod][i]!=father)
if(!viz[v[nod][i]])
{
stv[++j].x=nod;
stv[j].y=v[nod][i];
dfs(v[nod][i],nod,niv+1);
minniv[nod]=min(minniv[nod],minniv[v[nod][i]]);
if(minniv[v[nod][i]]>=niv1[nod])
{
vector <int> sol;
do
{
sol.push_back (stv[j].x);
sol.push_back (stv[j].y);
--j;
}
while((stv[j+1].x!=nod||stv[j+1].y!=v[nod][i])&&j>0);
S.push_back (sol);
++nr;
}
}
else
minniv[nod]=min(minniv[nod],niv1[v[nod][i]]);
}
}
int main()
{
fscanf(f,"%d%d",&n,&m);
for(int i=1;i<=m;++i)
{
fscanf(f,"%d%d",&x,&y);
v[x].push_back (y);
v[y].push_back (x);
}
dfs(1,0,1);
fprintf(g,"%d\n",nr);
for(int i=0;i<nr;++i){
S[i].push_back (200000);
sort(S[i].begin(),S[i].end());
int nr=S[i].size()-1;
for(int j=0;j<nr;++j)
if(S[i][j]!=S[i][j+1])
fprintf(g,"%d ",S[i][j]);
fprintf(g,"\n");
}
fclose(g);
fclose(f);
return 0;
}