Pagini recente » Cod sursa (job #124929) | Cod sursa (job #13228) | Cod sursa (job #1110561) | Cod sursa (job #2732406) | Cod sursa (job #3296155)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector<vector<int>> adj;
vector<int> depth;
vector<int> lowpoint;
stack<int> active;
vector<vector<int>> components;
void dfs(int v, int parent)
{
lowpoint[v] = depth[v];
active.push(v);
for (int sz : adj[v]) {
if (depth[sz] == -1) {
depth[sz] = depth[v]+1;
dfs(sz, v);
lowpoint[v] = min(lowpoint[v], lowpoint[sz]);
if (lowpoint[sz] >= depth[v]) {
vector<int> comp;
while (!active.empty() && active.top() != v) {
comp.push_back(active.top());
active.pop();
}
comp.push_back(v);
components.push_back(comp);
}
}
else if (sz != parent) {
lowpoint[v] = min(lowpoint[v], depth[sz]);
}
}
}
int main()
{
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m;
fin >> n >> m;
adj.resize(n+1);
depth.resize(n+1, -1);
lowpoint.resize(n+1, -1);
for (int i = 0; i < m; i++) {
int a, b;
fin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
depth[1] = 0;
dfs(1, -1);
for (int i = 1; i <= n; i++)
if (depth[i] == -1)
fout << "not connected...\n";
fout << components.size() << "\n";
for (auto &c : components) {
for (auto e : c) {
fout << e << " ";
}
fout << "\n";
}
return 0;
}