Pagini recente » Cod sursa (job #1411341) | Cod sursa (job #1000560) | Borderou de evaluare (job #1660147) | Cod sursa (job #3171493) | Cod sursa (job #957878)
Cod sursa(job #957878)
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
vector< pair<int,int> > G[100005];
const int INF=1000000000;
struct EDGE {int x,y;} edge[200005];
int edge_to_dad[100005];
bool critic[200005];
bool viz[100005];
vector<int> sol;
vector< vector<int> > cc;
int level[100005];
int dp[100005];
int t[100005];
int lvl,n,m;
int nr_critics;
void dfs(int u)
{
viz[u]=true;
level[u]=lvl++;
dp[u]=INF;
for(vector< pair<int,int> >::iterator it=G[u].begin();it!=G[u].end();it++)
if(!viz[it->first])
{
t[it->first]=u;edge_to_dad[it->first]=it->second;
dfs(it->first);
dp[u]=min(dp[u],dp[it->first]);
}
else if(it->first!=t[u])
dp[u]=min(dp[u],level[it->first]);
if(dp[u]>=level[u])
{
critic[edge_to_dad[u]]=true;
nr_critics++;
}
lvl--;
}
void dfs2(int u)
{
viz[u]=true;
sol.push_back(u);
for(vector< pair<int,int> >::iterator it=G[u].begin();it!=G[u].end();it++)
if(!viz[it->first] && !critic[it->second])
dfs2(it->first);
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&edge[i].x,&edge[i].y),
G[edge[i].x].push_back(make_pair(edge[i].y,i)),
G[edge[i].y].push_back(make_pair(edge[i].x,i));
for(int i=1;i<=n;i++)
if(!viz[i])
dfs(i),
--nr_critics;
memset(viz,0,sizeof viz);
for(int i=1;i<=n;i++)
if(!viz[i])
{
sol.clear();
dfs2(i);
if((int)sol.size()>1)
cc.push_back(sol);
}
printf("%d\n",nr_critics+(int)cc.size());
for(int i=0;i<(int)cc.size();i++)
for(int j=0;j<(int)cc[i].size();j++)
printf("%d%c",cc[i][j],j==(int)cc[i].size()-1?'\n':' ');
for(int i=1;i<=m;i++)
if(critic[i])
printf("%d %d\n",edge[i].x,edge[i].y);
return 0;
}