Pagini recente » Cod sursa (job #195863) | Cod sursa (job #862714) | Cod sursa (job #2910054) | Cod sursa (job #1992864) | Cod sursa (job #1376914)
#include <cstring>
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
typedef std::vector<int>::iterator iter;
const int INF = 0x3f3f3f3f;
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 parent[MAXN], low[MAXN], level[MAXN];
std::bitset<MAXN> viz;
std::pair<int, int> st[MAXN];
std::vector< std::vector<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 == parent[node]) {
continue;
}
if (viz[*it] == true) {
low[node] = min(low[node], level[*it]);
}
else {
parent[*it] = node;
st[++st[0].first] = make_pair(node, *it);
low[node] = min(low[node], dfs(*it, lv + 1));
}
}
if (low[node] >= level[parent[node]]) {
//cout << node << endl;
comps.push_back(vector<int>());
while (st[st[0].first] != make_pair(parent[node], node)) {
comps.back().push_back(st[st[0].first--].second);
}
comps.back().push_back(parent[node]);
comps.back().push_back(node);
}
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);
}
parent[1] = 0;
st[++st[0].first].first = 0;
dfs(1);
/*if (!st[0]) {
comps.push_back(std::vector<int>());
while (!st[0]) {
comps.back().push_back(st[st[0]--]);
}
}*/
g << comps.size() << '\n';
for (int i = 0; i < comps.size(); i++) {
for (iter it = comps[i].begin(); it != comps[i].end(); it++) {
g << *it << ' ';
}
g << '\n';
}
f.close();
g.close();
return 0;
}