Pagini recente » Cod sursa (job #2752594) | Cod sursa (job #134929) | Cod sursa (job #667267) | Cod sursa (job #1221530) | Cod sursa (job #957880)
Cod sursa(job #957880)
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<cstring>
#define NMAX 100000
#define MMAX 200000
using namespace std;
struct EDGE { int ind, v; };
vector <EDGE> graph[NMAX+10];
vector <int> biconex[NMAX+10];
const int kinf=2e9;
int nr,N,M,lvl,dp[NMAX+10],level[NMAX+10],dad[NMAX+10];
bool bad[MMAX+10];
int viz[NMAX+10];
EDGE m_edge (int a, int b)
{
EDGE aux;
aux.ind=a;
aux.v=b;
return aux;
}
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])
{
dad[graph[x][i].v]=x;
dfs(graph[x][i].v,graph[x][i].ind);
dp[x]=min(dp[x],dp[graph[x][i].v]);
}
else
if(graph[x][i].v!=dad[x])
dp[x]=min(dp[x],level[graph[x][i].v]);
if(dp[x]>=level[x])
bad[e]=1;
--lvl;
}
vector < pair<int,int> > o;
void alt_dfs (int x)
{
int i;
viz[x]=nr;
for(i=0;i<graph[x].size();i++)
if(!bad[graph[x][i].ind] && !viz[graph[x][i].v])
alt_dfs(graph[x][i].v);
else
if(bad[graph[x][i].ind] && !viz[graph[x][i].v])
o.push_back(make_pair(graph[x][i].v,x));
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int x,i,y,j,num;
scanf("%d%d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d%d",&x,&y);
graph[x].push_back(m_edge(i,y));
graph[y].push_back(m_edge(i,x));
}
lvl=0;
for(i=1;i<=N;i++)
if(!viz[i])
dfs(i,0);
memset(viz,0,sizeof(viz));
nr=0;
for(i=1;i<=N;i++)
if(!viz[i])
{
nr++;
alt_dfs(i);
}
for(i=1;i<=N;i++)
biconex[viz[i]].push_back(i);
for(i=0;i<o.size();i++)
biconex[++nr].push_back(o[i].first),
biconex[nr].push_back(o[i].second);
num=0;
for(i=1;i<=nr;i++)
if(biconex[i].size()>1)
num++;
printf("%d\n",num);
for(i=1;i<=nr;i++)
if(biconex[i].size()>1)
{
for(j=0;j<biconex[i].size();j++)
printf("%d ",biconex[i][j]);
printf("\n");
}
return 0;
}