Pagini recente » Cod sursa (job #2950304) | Cod sursa (job #945877) | Cod sursa (job #1848650) | Cod sursa (job #3148257) | Cod sursa (job #1225423)
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
const int INF = 2e9, NMAX = 1e5;
struct EDGE { int node, ind; };
vector <EDGE> graph[NMAX + 5];
vector <int> comp[NMAX +5];
int a[2 * NMAX + 5], b[2 * NMAX + 5], vis[NMAX + 5], critic[2 * NMAX + 5], level[NMAX + 5], dp[NMAX + 5], dad[NMAX + 5];
int n,lvl,cnt,res;
void dfs (int node, int edge) {
vector <EDGE>::iterator it;
vis[node] = 1;
dp[node] = INF;
level[node] = ++ lvl;
for(it = graph[node].begin(); it != graph[node].end(); it++)
if(!vis[it -> node]) {
dad[it -> node] = node;
dfs(it -> node, it -> ind);
dp[node] = min(dp[node], dp[it -> node]);
}
else
if(it -> node != dad[node])
dp[node] = min(dp[node], level[it -> node]);
if(dp[node] >= level[node])
critic[edge] = 1;
-- lvl;
}
void dfs2 (int node) {
vector <EDGE>::iterator it;
vis[node] = cnt;
comp[cnt].push_back(node);
for(it = graph[node].begin(); it != graph[node].end(); it++)
if(!critic[it -> ind] && !vis[it -> node])
dfs2(it -> node);
}
int main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
int m,i;
vector <int>::iterator it;
scanf("%d%d",&n,&m);
for(i = 1; i <= m; i++) {
scanf("%d%d",&a[i],&b[i]);
graph[a[i]].push_back({b[i],i});
graph[b[i]].push_back({a[i],i});
}
lvl = 0;
for(i = 1; i <= n; i++)
if(!vis[i])
dfs(i, 0);
memset(vis, 0, sizeof(vis));
for(i = 1; i <= n; i++)
if(!vis[i]) {
++ cnt;
dfs2(i);
}
for(i = 1; i <= m; i++)
if(critic[i]) {
++cnt;
comp[cnt].push_back(a[i]);
comp[cnt].push_back(b[i]);
}
/* res = cnt;
for(i = 1; i <= cnt; i++)
if(comp[i].size() < 2)
res--;*/
printf("%d\n",res);
for(i = 1; i <= cnt; i++)
if(comp[i].size() > 1) {
for(it = comp[i].begin(); it != comp[i].end(); it++)
printf("%d ",*it);
printf("\n");
}
return 0;
}