Pagini recente » Cod sursa (job #2244526) | Rating Odagiu Serban (OdagiuSerban) | Cod sursa (job #2635264) | Cod sursa (job #167888) | Cod sursa (job #797077)
Cod sursa(job #797077)
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
FILE *in = fopen("biconex.in", "r"), *out = fopen("biconex.out", "w");
int n, m, index, viz[100001], lowlink[100001], tata[100001], entry_time[100001];
vector <int> G[100001];
vector <vector <int> > sol;
stack <int> bcStack;
void DFS(int nod){
int i, adj;
bcStack.push(nod);
lowlink[nod] = entry_time[nod] = ++index;
viz[nod] = 1;
vector <int> newbc;
for (i = 0; i < (int)G[nod].size(); i++){
adj = G[nod][i];
if (!viz[adj]) {
tata[adj] = nod;
DFS(adj);
// la intoarcerea din recursie, lowlink[tata] = min lowlink[fii]
lowlink[nod] = min (lowlink[nod], lowlink[adj]);
}
// am intalnit o muchie de intoarcere
else if (tata[nod] != adj)
lowlink[nod] = min (lowlink[nod], lowlink[adj]);
}
if (lowlink[nod] == entry_time[nod]){
do {
adj = bcStack.top(), bcStack.pop();
newbc.push_back(adj);
}
while (nod != adj);
if (newbc.size() > 1)sol.push_back(newbc);
//daca este cazul, adauga comp biconexa formata din nodul de articulatie si tatal lui
if (tata[nod]){
newbc.clear();
newbc.push_back(nod), newbc.push_back(tata[nod]);
sol.push_back(newbc);
}
}
}
int main(){
int i, j, x, y;
fscanf(in, "%d %d", &n, &m);
for (i = 0; i <= m; i++){
fscanf(in, "%d %d", &x, &y);
G[x].push_back(y);
G[y].push_back(x);
}
for (i = 1; i <= n ;i++)
if (!viz[i]) DFS(i);
fprintf(out, "%d\n", sol.size());
for (i = 0; i < (int)sol.size(); i++){
for (j = 0; j < (int)sol[i].size(); j++)
fprintf(out, "%d ", sol[i][j]);
fprintf(out, "\n");
}
}