Pagini recente » Diferente pentru utilizator/bogdanisar intre reviziile 8 si 7 | Cod sursa (job #1920115)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 100000, kMaxM = 200000;
int Edge[kMaxM];
vector<int> G[kMaxN];
int Dfn[kMaxN];
pair<int, int> Stk[kMaxN];
vector<int> Component[kMaxN];
int numComponents;
int Dfs(int node) {
static int nextIdx = 0, stackSize = 0;
int minPtr = Dfn[node] = ++nextIdx;
for(const int& e : G[node]) {
int son = node ^ Edge[e];
if(Dfn[son] == 0) {
Stk[stackSize++] = {node, son};
int sonMinPtr = Dfs(son);
minPtr = min(minPtr, sonMinPtr);
if(Dfn[node] <= sonMinPtr) {
int x, y;
do {
x = Stk[stackSize - 1].first;
y = Stk[stackSize - 1].second;
Component[numComponents].emplace_back(x);
Component[numComponents].emplace_back(y);
stackSize--;
} while (x != node || y != son);
numComponents++;
}
} else
minPtr = min(minPtr, Dfn[son]);
}
return minPtr;
}
int main() {
#ifdef INFOARENA
ifstream cin("biconex.in");
ofstream cout("biconex.out");
#endif
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for(int i = 0; i < m; ++i) {
int x, y;
cin >> x >> y;
x--; y--;
G[x].push_back(i);
G[y].push_back(i);
Edge[i] = x ^ y;
}
for(int i = 0; i < n; ++i)
if(!Dfn[i])
Dfs(i);
cout << numComponents << '\n';
for(int i = 0; i < numComponents; ++i) {
sort(begin(Component[i]), end(Component[i]));
Component[i].erase(unique(begin(Component[i]), end(Component[i])), end(Component[i]));
for(const int& x : Component[i])
cout << x + 1 << ' ';
cout << '\n';
}
}