Pagini recente » Cod sursa (job #2472329) | Cod sursa (job #1999572) | Cod sursa (job #2390543) | Cod sursa (job #2547028) | Cod sursa (job #2668523)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector < int > id, low_id;
vector < vector < int > > G, Components;
stack < pair < int , int > > S;
inline void min_self(int& a, int b) {
a = min(a, b);
}
void BC(int u, int v) {
vector < int > new_c;
int x, y;
do {
x = S.top().first, y = S.top().second;
S.pop();
new_c.emplace_back(x), new_c.emplace_back(y);
} while(x != u || y != v);
Components.emplace_back(new_c);
}
void DFS(int node, int parent, int val) {
id[node] = low_id[node] = val;
for(int vec : G[node]) {
if(vec == parent)
continue;
if(id[vec] == -1) {
S.emplace(node, vec);
DFS(vec, node, val + 1);
min_self(low_id[node], low_id[vec]);
if(low_id[vec] >= id[node])
BC(node, vec);
}
else
min_self(low_id[node], id[vec]);
}
}
int main() {
int N, M;
fin >> N >> M;
G.resize(N + 1), id.assign(N + 1, -1), low_id.resize(N + 1);
while(M--) {
int u, v;
fin >> u >> v;
G[u].emplace_back(v);
G[v].emplace_back(u);
}
DFS(1, 0, 0);
fout << Components.size() << '\n';
for(auto C : Components) {
sort(C.begin(), C.end());
C.erase(unique(C.begin(), C.end()), C.end());
for(int node : C)
fout << node << ' ';
fout << '\n';
}
}