Pagini recente » Cod sursa (job #2438415) | Cod sursa (job #2161011) | Cod sursa (job #977287) | Cod sursa (job #2636366) | Cod sursa (job #1631182)
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <iomanip>
#define MOD 9917
#define NMAX 100005
#define INF 0x3f3f3f3f
#define pb push_back
using namespace std;
FILE *fin = freopen("biconex.in", "r", stdin);
FILE *fout = freopen("biconex.out", "w", stdout);
typedef pair<int, int> pii;
vector<int> v[NMAX];
int dfn[NMAX], low[NMAX], nr;
vector<vector<int> > C;
stack<pii> st;
void DFS(int x, int p);
void add_comp(int x, int y);
int main() {
int n, i, x, y, a, b, sum = 0, m, j;
cin >> n >> m;
for (i = 0; i<m; ++i) {
cin >> x >> y;
v[x].pb(y);
v[y].pb(x);
}
memset(dfn, -1, sizeof(dfn));
DFS(1, 0);
cout << C.size() << '\n';
for (i = 0; i<C.size(); ++i) {
sort(C[i].begin(), C[i].end());
for (j = 0; j<C[i].size(); ++j)
if (j == 0 || j>0 && C[i][j] != C[i][j - 1])
cout << C[i][j] << ' ';
cout << '\n';
}
return 0;
}
void add_comp(int x, int y) {
int x1, y1;
vector<int> comp;
do {
x1 = st.top().first;
y1 = st.top().second;
st.pop();
comp.pb(x1);
comp.pb(y1);
} while (x1 != x || y1 != y);
C.pb(comp);
}
void DFS(int x, int p) {
vector<int>::iterator it;
dfn[x] = low[x] = nr++;
for (it = v[x].begin(); it != v[x].end(); ++it) {
if (*it == p)
continue;
if (dfn[*it] == -1) {
st.push({ x, *it });
DFS(*it, x);
low[x] = min(low[x], low[*it]);
if (low[*it] >= dfn[x])
add_comp(x, *it);
}
else
low[x] = min(low[x], dfn[*it]);
}
}