Pagini recente » Cod sursa (job #710928) | Cod sursa (job #1687503) | Cod sursa (job #1551358) | Cod sursa (job #183788) | Cod sursa (job #3210015)
#include <bits/stdc++.h>
#define NMAX 100002
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int n, m, level[NMAX], minlevel[NMAX], root = 1;
vector<int> G[NMAX];
bitset<NMAX> viz;
stack<pair<int, int>> edges;
vector<unordered_set<int>> biconnected_components;
void read_data()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
}
void extract_biconected_components(int nod, int vec)
{
unordered_set<int> bc;
pair<int, int> edge;
do {
edge = edges.top();
edges.pop();
bc.insert(edge.first);
bc.insert(edge.second);
}
while(edge.first != nod && edge.second != vec);
biconnected_components.push_back(bc);
}
void dfs(int nod, int dad)
{
viz[nod] = true;
level[nod] = level[dad] + 1;
minlevel[nod] = level[dad] + 1;
for (auto vec : G[nod])
{
if (vec == dad) continue;
if (viz[vec] == true)
{
// back edge
minlevel[nod] = min(minlevel[nod], level[vec]);
}
else
{
// tree edge
edges.push(make_pair(nod, vec));
dfs(vec, nod);
minlevel[nod] = min(minlevel[nod], minlevel[vec]);
if (minlevel[vec] >= level[nod])
extract_biconected_components(nod, vec);
}
}
}
void print()
{
fout << biconnected_components.size() << "\n";
for (auto bc : biconnected_components)
{
for (auto nod : bc)
fout << nod << " ";
fout << "\n";
}
fout << "\n";
}
int main()
{
read_data();
dfs(root, 0);
print();
return 0;
}