Pagini recente » Cod sursa (job #557048) | Cod sursa (job #2246598) | Cod sursa (job #442352) | Cod sursa (job #2399302) | Cod sursa (job #2203543)
// https://goo.gl/fBmFxu
#include <bits/stdc++.h>
using namespace std;
#define NMAX 100009
#define MMAX 200009
#define kInf (1 << 30)
#define kInfLL (1LL << 60)
#define kMod 666013
#define edge pair<int, int>
#define x first
#define y second
// number of tests from "in"
int test_cnt = 1;
void clean_test();
// your global variables are here
int n, m;
vector<int> G[NMAX];
int T[NMAX];
vector<int> cv;
vector<edge> ce;
stack<edge> st;
vector<vector<int> > all_bcc;
int current_start;
int found[NMAX], low_link[NMAX];
template<typename T>
void make_unique(vector<T> &v) {
sort(v.begin(), v.end());
auto it = unique(v.begin(), v.end());
v.erase(it, v.end());
}
void get_bcc(edge target) {
vector<int> bcc;
edge e;
do {
e = st.top();
st.pop();
bcc.push_back(e.first);
bcc.push_back(e.second);
} while (e != target);
make_unique(bcc);
all_bcc.push_back(bcc);
}
void dfs(int node) {
int children = 0;
found[node] = low_link[node] = ++current_start;
for (auto &x : G[node]) {
if (!T[x]) {
++children;
T[x] = node;
st.push({node, x});
dfs(x);
low_link[node] = min(low_link[node], low_link[x]);
// cut vertex
if (T[node] != node && low_link[x] >= found[node]) {
cv.push_back(node);
}
// critical edge
if (low_link[x] > found[node]) {
ce.push_back({node, x});
}
if (low_link[x] >= found[node]) {
get_bcc({node, x});
}
} else {
if (T[x] != node) {
low_link[node] = min(low_link[node], found[x]);
}
}
}
if (T[node] == node && children > 1) {
cv.push_back(node);
}
}
void tarjan() {
for (int i = 1; i <= n; ++i) {
if (!T[i]) {
T[i] = i;
dfs(i);
}
}
make_unique(cv);
make_unique(ce);
}
// your solution is here
void solve() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
tarjan();
cout << all_bcc.size() << "\n";
for (auto &bcc : all_bcc) {
for (auto &x : bcc) {
cout << x << " ";
}
cout << "\n";
}
if (test_cnt > 0) {
clean_test();
}
}
void clean_test() {
// clean if needed
memset(T, 0, sizeof(T));
cv.clear();
ce.clear();
all_bcc.clear();
for (int i = 1; i <= n; ++i) {
if (G[i].size()) {
G[i].clear();
}
}
// clean every shit
n = m = 0;
}
int main() {
// din cauza ca fac redirectari, salvez starea lui cin si cout
auto cin_buff = cin.rdbuf();
auto cout_buff = cout.rdbuf();
// las liniile urmatoare daca citesc din fisier
ifstream fin("biconex.in");
cin.rdbuf(fin.rdbuf()); // save and redirect
// las liniile urmatoare daca afisez in fisier
ofstream fout("biconex.out");
cout.rdbuf(fout.rdbuf()); // save and redirect
// cin >> test_cnt;
while (test_cnt--) {
solve();
}
// restore pentru cin si cout
cin.rdbuf(cin_buff);
cout.rdbuf(cout_buff);
return 0;
}