Pagini recente » Cod sursa (job #302947) | Cod sursa (job #1397049) | Cod sursa (job #2702338) | Cod sursa (job #562826) | Cod sursa (job #957883)
Cod sursa(job #957883)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<string.h>
using namespace std;
struct edge
{
int v,e;
edge(int x1, int y1){
v = x1;
e = y1;
}
};
vector <edge> graph[100002];
const int kinf=2e9;
int viz[100002],lvl,dp[100002],t[100002],level[100002],bad[200002];
vector <vector<int> > ans;
vector <int> st;
void dfs2(int x)
{
int i;
st.push_back(x);
viz[x]=1;
for(i=0;i<graph[x].size();i++)
if(!viz[graph[x][i].v]&&!bad[graph[x][i].e])
dfs2(graph[x][i].v);
else
if(!viz[graph[x][i].v]&&bad[graph[x][i].e])
{
vector <int> a;
a.push_back(x);
a.push_back(graph[x][i].v);
ans.push_back(a);
}
}
void dfs(int x,int e)
{
int i;
viz[x]=1;
++lvl;
level[x]=lvl;
dp[x]=kinf;
for(i=0;i<graph[x].size();++i)
{
if(!viz[graph[x][i].v])
{
t[graph[x][i].v] = x;
dfs(graph[x][i].v,graph[x][i].e);
dp[x]=min(dp[x],dp[graph[x][i].v]);
}
else if(graph[x][i].v!=t[x])
dp[x]=min(dp[x],level[graph[x][i].v]);
}
if(dp[x]>=level[x])
bad[e]=1;
--lvl;
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int n,m,i,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
graph[x].push_back(edge(y,i));
graph[y].push_back(edge(x,i));
}
for(i=1;i<=n;i++)
if(!viz[i])
dfs(i,0);
memset(viz,0,sizeof(viz));
for(i=1;i<=n;i++)
if(!viz[i])
{
st.clear();
dfs2(i);
if(st.size()>1)
ans.push_back(st);
}
printf("%d\n",ans.size());
for(i=0;i<ans.size();i++)
{
for(int j=0;j<ans[i].size();j++)
printf("%d ",ans[i][j]);
printf("\n");
}
return 0;
}