Pagini recente » Cod sursa (job #1052738) | Cod sursa (job #1354977) | Cod sursa (job #547197) | Cod sursa (job #2648355) | Cod sursa (job #1965780)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector<int> v[100003];
int disc[100003];
int low[100003];
int parent[100003];
stack<pair<int, int>> S;
int tim;
vector<int> C[100003];
int am;
void magic(int x, int y) {
int tx,ty;
am++;
do {
if(S.empty())
return;
tx = S.top().first;
ty = S.top().second;
C[am].push_back(tx);
C[am].push_back(ty);
S.pop();
} while(tx != x || ty != y);
}
void dfs(int nod) {
disc[nod] = ++tim;
low[nod] = disc[nod];
int nx;
for(int i = 0; i < v[nod].size(); i++) {
nx = v[nod][i];
//cout << nod << " " << nx << " " << parent[nx] << '\n';
if(disc[nx] == 0) {
S.push({nod, nx});
parent[nx] = nod;
dfs(nx);
low[nod] = min(low[nod], low[nx]);
//cout << nod << " " << nx << " " << disc[nod] << " " << low[nx] << '\n';
if(disc[nod] <= low[nx])
magic(nod, nx);
} else if(parent[nod] != nx)
low[nod] = min(low[nod], low[nx]);
}
}
int main() {
int n,m;
in >> n >> m;
int x,y;
for(int i = 1; i <= m; i++) {
in >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
for(int i = 1; i <= n; i++) {
if(disc[i] == 0)
dfs(i);
if(!S.empty())
magic(0,0);
}
out << am << '\n';
for(int i = 1; i <= am; i++) {
sort(C[i].begin(), C[i].end());
C[i].resize(distance(C[i].begin(), unique(C[i].begin(), C[i].end())));
for(int j = 0; j < C[i].size(); j++)
out << C[i][j] << " ";
out << '\n';
}
return 0;
}