Pagini recente » Cod sursa (job #1989019) | Cod sursa (job #2498456) | Cod sursa (job #2698135) | Cod sursa (job #2589657) | Cod sursa (job #457217)
Cod sursa(job #457217)
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define maxn 100010
#define inf 99999999
int N, M, Nr;
int low[maxn], lev[maxn];
vector<int> G[maxn], CC[maxn];
stack<pair<int, int> > S;
void CompB(int x, int y) {
Nr++;
int i, j;
i = S.top().first;
j = S.top().second;
S.pop();
CC[Nr].push_back(i); CC[Nr].push_back(j);
while(i != x || j != y) {
i = S.top().first;
j = S.top().second;
S.pop();
CC[Nr].push_back(i); CC[Nr].push_back(j);
}
}
void DFS(int nod, int prev) {
lev[nod] = lev[prev] + 1;
low[nod] = inf;
for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
if((*it) != prev) {
if(!lev[(*it)]) {
S.push(make_pair(nod, *it));
DFS(*it, nod);
low[nod] = min(low[nod], low[*it]);
if(low[*it] >= lev[nod]) {
CompB(nod, *it);
}
}
else {
low[nod] = min(low[nod], lev[*it]); //muchie de intoarcere
}
}
}
}
int main() {
FILE *f1=fopen("biconex.in", "r"), *f2=fopen("biconex.out", "w");
int i, j, p;
fscanf(f1, "%d %d\n", &N, &M);
for(i=1; i<=M; i++) {
fscanf(f1, "%d %d\n", &j, &p);
G[j].push_back(p);
G[p].push_back(j);
}
DFS(1, 0);
fprintf(f2, "%d\n", Nr);
for(i=1; i<=Nr; i++) {
sort(CC[i].begin(), CC[i].end());
CC[i].erase(unique(CC[i].begin(), CC[i].end()), CC[i].end());
for(j=0; j<CC[i].size(); j++) {
fprintf(f2, "%d ", CC[i][j]);
}
fprintf(f2, "\n");
}
fclose(f1); fclose(f2);
return 0;
}