Pagini recente » Cod sursa (job #2481634) | Cod sursa (job #1393402) | Cod sursa (job #2845647) | Cod sursa (job #2319990) | Cod sursa (job #2195444)
#include <bits/stdc++.h>
#define NMAX 100010
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> G[NMAX];
stack < pair <int, int> > Q;
vector < vector <int> > components;
vector <bool> visited;
vector <int> niv, nivmin;
void biconnected_component(int x, int y) {
int a, b;
components.push_back(vector<int>());
do {
a = Q.top().first;
b = Q.top().second;
Q.pop();
components.back().push_back(b);
} while(a != x or b != y);
components.back().push_back(x);
}
void DFS(int x, int level) {
niv[x] = nivmin[x] = level;
visited[x] = true;
for (vector <int> :: iterator it = G[x].begin(); it != G[x].end(); ++it) {
if (visited[(*it)] == false) {
Q.push(make_pair(x, (*it)));
DFS((*it), level + 1);
nivmin[x] = min(nivmin[x], nivmin[(*it)]);
if (nivmin[(*it)] >= niv[x]) {
biconnected_component(x, (*it));
}
}
else {
nivmin[x] = min(nivmin[x], niv[(*it)]);
}
}
}
int main() {
int N, M;
fin >> N >> M;
for (int x, y, i = 0; i < M; ++i) {
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
visited.resize(N + 1, false);
niv.resize(N + 1);
nivmin.resize(N + 1);
for (int i = 1; i <= N; ++i) {
if (visited[i] == false) {
DFS(i, 0);
}
}
fout << components.size() << '\n';
for (int i = 0; i < components.size(); ++i) {
for (auto it = components[i].begin(); it != components[i].end(); ++it) {
fout << *it << ' ';
}
fout << '\n';
}
return 0;
}