Pagini recente » Cod sursa (job #56453) | Cod sursa (job #239593) | Cod sursa (job #265037) | Cod sursa (job #1543932) | Cod sursa (job #1537226)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000 + 1;
const int MAX_M = 200000 + 1;
stack< pair<int,int> > stiva;
vector<vector<int>>BC;
vector<int> G[MAX_N];
int lowLink[MAX_N];
int dfn[MAX_N];
int N, M;
void biconex(int x, int y)
{
vector<int> v;
pair<int,int> p;
do
{
p = stiva.top();
stiva.pop();
v.push_back(p.first);
v.push_back(p.second);
} while (p.first != x || p.second != y);
BC.push_back(v);
}
void dfs(int node, int nr)
{
lowLink[node] = dfn[node] = nr;
for (int son : G[node])
{
if (dfn[son] == 0)
{
stiva.push({node, son});
dfs(son, nr + 1);
lowLink[node] = min(lowLink[node], lowLink[son]);
if (lowLink[son] >= dfn[node])
{
biconex(node, son);
}
}
else
lowLink[node] = min(lowLink[node], dfn[son]);
}
}
int main()
{
ifstream in("biconex.in");
ofstream out("biconex.out");
in >> N >> M;
for (int i = 1; i <= M; ++i)
{
int x, y;
in >> x >> y;
G[x].emplace_back(y);
G[y].emplace_back(x);
}
for (int i = 1; i <= N; ++i)
if (dfn[i] == 0)
dfs(i, 1);
out << BC.size() << "\n";
for (auto v : BC)
{
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int x : v)
out << x << " ";
out << "\n";
}
return 0;
}