Pagini recente » Cod sursa (job #611679) | Cod sursa (job #2160550) | Cod sursa (job #197826) | Cod sursa (job #542143) | Cod sursa (job #1920950)
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
#include <climits>
#define NMAX 100005
using namespace std;
int N, M, nrComp;
vector<int> G[NMAX], inStack, comp[NMAX];
stack<int> S;
vector<bool> utilised;
int DFS(int node) {
int pos = S.size() + 1, min1 = S.size() + 1, min2 = INT_MAX;
S.push(node);
utilised[node] = true;
inStack[node] = S.size();
for(int i = 0; i < G[node].size(); i++) {
int neigh = G[node][i];
if(!utilised[neigh]) {
int dist = DFS(neigh);
min1 = min(min1, dist);
if(dist == pos) {
nrComp++;
while(1) {
comp[nrComp].push_back(S.top());
int TopBeforePop = S.top();
inStack[S.top()] = 0;
S.pop();
if(TopBeforePop == neigh) break;
}
comp[nrComp].push_back(node);
}
}
else if(inStack[neigh]) min2 = min(min2, inStack[neigh]);
}
return min(min1, min2);
}
int main() {
freopen("biconex.in", "rt", stdin);
freopen("biconex.out", "wt", stdout);
scanf("%d%d", &N, &M);
while(M--) {
int u, v;
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
utilised.assign(N + 2, false);
inStack.assign(N + 2, 0);
DFS(1);
cout << nrComp << '\n';
for(int c = 1; c <= nrComp; c++) {
for(int j = 0; j < comp[c].size(); j++)
cout << comp[c][j] << ' ';
cout << '\n';
}
}