Pagini recente » Cod sursa (job #2402666) | Cod sursa (job #2123147) | Cod sursa (job #186475) | Cod sursa (job #1221345) | Cod sursa (job #1377068)
#include <cstring>
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <stack>
#include <set>
typedef std::vector<int>::iterator iter;
typedef std::set<int>::iterator siter;
const int MAXN = 100005;
const int MAXM = 200005;
std::ifstream f("biconex.in");
std::ofstream g("biconex.out");
std::vector<int> G[MAXN]; int n, m;
int t[MAXN];
int low[MAXN];
int level[MAXN];
std::bitset<MAXN> viz;
std::stack< std::pair<int, int> > st;
std::vector< std::set<int> > comps;
int dfs(int node, int lv = 1)
{
viz[node] = true;
level[node] = lv;
low[node] = lv;
for (iter it = G[node].begin(); it != G[node].end(); it++) {
if (*it == t[node]) {
continue;
}
if (viz[*it] == true) {
low[node] = std::min(low[node], level[*it]);
}
else {
t[*it] = node;
st.push(std::make_pair(node, *it));
low[node] = std::min(low[node], dfs(*it, lv + 1));
}
}
if (low[node] >= level[t[node]]) {
comps.push_back(std::set<int>());
while (st.top() != std::make_pair(t[node], node)) {
comps.back().insert(st.top().first);
comps.back().insert(st.top().second);
st.pop();
}
comps.back().insert(t[node]);
comps.back().insert(node);
st.pop();
}
return low[node];
}
int main()
{
memset(level, 0x3f, sizeof(level));
memset(low, 0x3f, sizeof(low));
f >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
g << comps.size() << '\n';
for (int i = 0; i < comps.size(); i++) {
for (siter it = comps[i].begin(); it != comps[i].end(); it++) {
g << *it << ' ';
}
g << '\n';
}
f.close();
g.close();
return 0;
}