Pagini recente » Cod sursa (job #3170783) | Cod sursa (job #1641878) | Cod sursa (job #2537844) | Cod sursa (job #1777100) | Cod sursa (job #2610568)
#include<stdio.h>
#include<vector>
using namespace std;
const int MAXN = 100001;
vector <int> g[MAXN], dfs_st;
bool viz[MAXN];
bool onS[MAXN];
int pozS[MAXN];
int dad[MAXN];
int min_back[MAXN];
vector <vector <int>> sol;
FILE *in, *out;
void get_bcc(int v) {
vector<int> rez = vector<int> ();
while(dfs_st.back() != v) {
rez.push_back(dfs_st.back());
onS[dfs_st.back()] = false;
dfs_st.pop_back();
}
rez.push_back(v);
sol.push_back(rez);
}
void tarj(int n, int d) {
/*
printf("pre %d: ", n);
for(auto &it : dfs_st) {
printf("%d ", it);
}
printf("\n");
*/
//printf("eu %d, sunt la %d pe sitva\n", n, dfs_st.size());
viz[n] = true;
min_back[n] = dfs_st.size();
pozS[n] = dfs_st.size();
dfs_st.push_back(n);
onS[n] = true;
for(auto &it : g[n]) {
if(!viz[it]) {
dad[it] = n;
tarj(it, d + 1);
//printf("in %d, it = %d returns x = %d\n", n, it, min_back[it]);
if(min_back[it] == pozS[n]) {
get_bcc(n);
}
min_back[n] = min(min_back[n], min_back[it]);
} else {
if(onS[it]) {
if(dad[n] != 0) {
if(it != dad[n]) {
min_back[n] = min(min_back[n], pozS[it]);
}
}
}
}
}
/*
printf("rec %d: ", n);
for(auto &it : dfs_st) {
printf("%d ", it);
}
printf("\n");
*/
if(min_back[n] == pozS[n]) {
min_back[n] = pozS[dad[n]];
}
if(dad[n] == 0 && g[n].size() == 0) {
get_bcc(n);
}
/*
printf("fin %d: ", n);
for(auto &it : dfs_st) {
printf("%d ", it);
}
printf("\n");
*/
}
int main () {
in = fopen("biconex.in", "r");
out = fopen("biconex.out", "w");
int n, m;
fscanf(in, "%d %d", &n, &m);
for(int i = 0; i < m; i++) {
int x, y;
fscanf(in, "%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
fclose(in);
for(int i = 1; i <= n; i++) {
if(!viz[i]) {
dad[i] = 0;
tarj(i, 0);
dfs_st.pop_back();
onS[i] = false;
}
}
fprintf(out, "%d\n", sol.size());
for(auto &bcc : sol) {
for(auto &elem : bcc) {
fprintf(out, "%d ", elem);
}
fprintf(out, "\n");
}
fclose(out);
return 0;
}