Pagini recente » Cod sursa (job #2475855) | Istoria paginii runda/budescupleaca/clasament | Cod sursa (job #2120941) | Cod sursa (job #2747427) | Cod sursa (job #632018)
Cod sursa(job #632018)
#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
#define MAXN 100005
int n,m;
vector<int> g[MAXN];
int depth[MAXN],low[MAXN],parent[MAXN];
bool viz[MAXN];
vector<vector<int>> rez;
struct edge {
int x,y;
};
stack<edge> st;
void output(int u,int v) {
edge e;
vector<int> r;
do {
e = st.top();
st.pop();
r.push_back(e.y);
} while (e.x != u && e.y != v);
if (r.size() == 1) {
r.push_back(e.x);
}
rez.push_back(r);
}
void dfs(int node,int d) {
viz[node] = 1;
depth[node] = d;
low[node] = d;
for (int i = 0 ; i < g[node].size() ; ++i) {
if (!viz[g[node][i]]) {
edge e;
e.x = node;
e.y = g[node][i];
st.push(e);
parent[g[node][i]] = node;
dfs(g[node][i],d + 1);
if (low[g[node][i]] >= depth[node]) {
output(node,g[node][i]);
}
low[node] = min(low[node],low[g[node][i]]);
} else if (g[node][i] != parent[node] && depth[g[node][i]] < depth[node]) {
edge e;
e.x = node;
e.y = g[node][i];
st.push(e);
low[node] = min(low[node],depth[g[node][i]]);
}
}
}
int main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
int x,y;
for (int i = 0 ; i < m ; ++i) {
scanf("%d %d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n ; ++i) {
if (!viz[i]) {
dfs(i,1);
}
}
printf("%d\n",rez.size());
for (int i = 0; i < rez.size() ; ++i) {
for (int j = 0 ; j < rez[i].size() ; ++j) {
printf("%d ",rez[i][j]);
}
printf("\n");
}
return 0;
}