Pagini recente » Cod sursa (job #151255) | Cod sursa (job #426375) | Cod sursa (job #3263608) | Cod sursa (job #35098) | Cod sursa (job #1519212)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 100000 + 1;
vector<int> G[MAX_N];
vector<int> BC[MAX_N];
stack< pair<int,int> > stiva;
int lowLink[MAX_N];
int dfn[MAX_N];
bool visited[MAX_N];
int N, M, numberBC;
void biconex(int node, int v)
{
pair<int,int> p;
do
{
p = stiva.top();
stiva.pop();
BC[ numberBC ].emplace_back(p.first);
BC[ numberBC ].emplace_back(p.second);
} while (p.first != node || p.second != v);
numberBC++;
}
void dfs(int node, int id)
{
dfn[node] = id;
lowLink[node] = id;
visited[node] = true;
for (int v : G[node])
{
if (visited[v] == 0)
{
stiva.push({node, v});
dfs(v, id + 1);
lowLink[node] = min(lowLink[node], lowLink[v]);
if (lowLink[v] >= dfn[node])
{
biconex(node, v);
}
}
else
lowLink[node] = min(lowLink[node], dfn[v]);
}
}
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 (!visited[i])
dfs(i, 1);
out << numberBC << "\n";
for (int i = 0; i < numberBC; ++i)
{
sort(BC[i].begin(), BC[i].end());
BC[i].erase(unique(BC[i].begin(), BC[i].end()), BC[i].end());
for (int x : BC[i])
out << x << " ";
out << "\n";
}
return 0;
}