Pagini recente » Cod sursa (job #2287314) | Cod sursa (job #1837817) | Cod sursa (job #2410063) | Cod sursa (job #206775) | Cod sursa (job #2668090)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<vector<int>> adiacente;
vector<int> lowlink, depth;
vector<set<int>> components;
int n, m;
stack<pair<int, int>> stiva;
void component(const pair<int, int> &edge)
{
pair<int, int> topStack;
set<int> BC;
do
{
topStack = stiva.top();
stiva.pop();
BC.insert(topStack.first);
BC.insert(topStack.second);
} while (topStack != edge);
components.push_back(BC);
}
void DFS(int node, int parent, int d)
{
depth[node] = lowlink[node] = d;
for (const int &nei : adiacente[node])
if (nei != parent)
{
if (depth[nei] == 0)
{
stiva.push(make_pair(node, nei));
DFS(nei, node, d + 1);
lowlink[node] = min(lowlink[node], lowlink[nei]);
if (lowlink[nei] >= depth[node])
component(make_pair(node, nei));
}
else
lowlink[node] = min(lowlink[node], depth[nei]);
}
}
int main()
{
fin >> n >> m;
adiacente.resize(n + 1);
lowlink.resize(n + 1);
depth.resize(n + 1);
components.reserve(n);
for (int e = 0; e < m; ++e)
{
int u, v;
fin >> u >> v;
adiacente[u].push_back(v);
adiacente[v].push_back(u);
}
for (int node = 1; node <= n; ++node)
if (depth[node] == 0)
DFS(node, 0, 1);
components.resize(components.size());
fout << components.size() << '\n';
for (int c = 0; c < (int)components.size(); ++c)
{
for (const int &node : components[c])
fout << node << ' ';
fout << '\n';
}
return 0;
}