Pagini recente » Cod sursa (job #2616172) | Cod sursa (job #2408360) | Cod sursa (job #1441597) | Cod sursa (job #3189582) | Cod sursa (job #3296157)
#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;
bool go = true;
while (!active.empty() && go) {
comp.push_back(active.top());
if (active.top() == sz) {
go = false;
}
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;
}