Pagini recente » Cod sursa (job #182675) | Cod sursa (job #453327) | Cod sursa (job #2405643) | Cod sursa (job #376503) | Cod sursa (job #2610569)
#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) {
/*
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);
//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]) {
min_back[n] = min(min_back[n], pozS[it]);
}
}
}
/*
printf("rec %d: ", n);
for(auto &it : dfs_st) {
printf("%d ", it);
}
printf("\n");
*/
if(dad[n] == 0 && g[n].size() == 0) {
get_bcc(n);
onS[n] = false;
dfs_st.pop_back();
}
/*
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);
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;
}