Pagini recente » Cod sursa (job #2155273) | Cod sursa (job #2133085) | Cod sursa (job #2752450) | Cod sursa (job #714743) | Cod sursa (job #2174010)
#include <cstdio>
#include <vector>
#include <stack>
using namespace std;
#define NMAX 100005
#define INF 2000000005
typedef pair<int, int> ii;
int n, m, solsz, time, d[NMAX], t[NMAX], low[NMAX];
vector<int> a[NMAX], sol[NMAX];
stack<ii> st;
void biconex(int source, int child) {
solsz++;
ii aux;
aux.first = st.top().first;
aux.second = st.top().second;
while(aux.first != source && aux.second != child) {
sol[solsz].push_back(aux.second);
st.pop();
aux.first = st.top().first;
aux.second = st.top().second;
}
st.pop();
sol[solsz].push_back(aux.second);
sol[solsz].push_back(aux.first);
}
void DFS(int nod) {
int i, child;
time++;
d[nod] = low[nod] = time;
for(i=0; i<(int) a[nod].size(); i++) {
child = a[nod][i];
if(child != t[nod]) {
if(!d[child]) {
st.push( ii(nod, child) );
t[child] = nod;
DFS(child);
if(low[child] >= d[nod])
biconex( nod, child );
low[nod] = min( low[nod], low[child] );
}
else {
low[nod] = min(low[nod], d[child]);
}
}
}
}
int main(){
int i, j, x, y;
FILE *fin, *fout;
fin = fopen("biconex.in", "r");
fout = fopen("biconex.out", "w");
fscanf(fin, "%d %d", &n, &m);
for(i=1; i<=m; i++) {
fscanf(fin, "%d %d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
for(i=1; i<=n; i++) {
if(!d[i])
DFS(i);
}
fprintf(fout, "%d\n", solsz);
for(i=1; i<=solsz; i++) {
for(j=0; j<(int) sol[i].size(); j++)
fprintf(fout, "%d ", sol[i][j]);
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
return 0;
}