Pagini recente » Cod sursa (job #2408225) | Cod sursa (job #2653180) | Cod sursa (job #838160)
Cod sursa(job #838160)
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn = 100010;
int nrc;
vector <int> g[maxn], c[maxn];
stack <pair <int, int > > ST;
int low[maxn], dfn[maxn];
int n;
void solve(int x, int y) {
++nrc;
int xx, yy;
do {
xx = ST.top().first;
yy = ST.top().second;
c[nrc].push_back(xx); c[nrc].push_back(yy);
ST.pop();
} while(xx != x || yy != y);
}
void dfs(int node, int f, int depth) {
dfn[node] = low[node] = depth;
for(vector <int> :: iterator it = g[node].begin(); it != g[node].end(); ++it) {
if(*it == f) continue;
if(dfn[*it] == -1) {
ST.push(make_pair(node, *it));
dfs(*it, node, depth + 1);
low[node] = min(low[node], low[*it]);
if(low[*it] >= dfn[node]) {
// printf("asdsadsadas\n");
solve(node, *it);
}
}
else low[node] = min(low[node], dfn[*it]);
}
}
void print() {
printf("%d\n", nrc);
for(int i = 1; i <= nrc; ++i) {
sort(c[i].begin(), c[i].end());
c[i].erase(unique(c[i].begin(), c[i].end()) , c[i].end());
}
for(int i = 1; i <= nrc; ++i) {
for(vector <int> :: iterator it = c[i].begin(); it != c[i].end(); ++it)
printf("%d ", *it);
printf("\n");
}
}
int main() {
freopen("biconex.in", "r", stdin);
freopen("biconex.out", "w", stdout);
int m, x, y;
for( scanf("%d %d\n", &n, &m); m--; ) {
scanf("%d %d\n", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
memset(dfn, -1, sizeof(dfn));
dfs(1, 0, 1);
/*
for(int i = 1; i <= n; ++i)
printf("%d ", low[i]);
printf("\n");
for(int i = 1;i <= n; ++i)
printf("%d ", dfn[i]);
*/ print();
return 0;
}