Pagini recente » Cod sursa (job #923529) | Cod sursa (job #2215790) | Cod sursa (job #1750665) | Cod sursa (job #374553) | Cod sursa (job #716751)
Cod sursa(job #716751)
// http://infoarena.ro/problema/biconex
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
#include <set>
using namespace std;
#define from first
#define to second
const int MAXSIZE = 100001;
ifstream in("biconex.in");
ofstream out("biconex.out");
/*
Folosim set pentru a evita inserarea
si verificarea ulterioara a unui nod
in lista nodurilor care formeaza
componenta biconexa
*/
int currentNodes,edges;
int depth[MAXSIZE],lowPoint[MAXSIZE];
vector< vector<int> > graph;
vector< set<int> > components;
stack< pair<int,int> > nodesStack;
void depthFirst(int currentNode, int currentDepth,int father);
int main() {
in >> currentNodes >> edges;
graph.resize(currentNodes+1);
int from,to;
for(int i=1;i<=edges;i++) {
in >> from >> to;
graph[from].push_back(to);
graph[to].push_back(from);
}
in.close();
depthFirst(1,1,-1);
out << components.size() << "\n";
vector< set<int> >::iterator it,end = components.end();
for(it=components.begin();it!=end;++it) {
set<int>::iterator node,endC = it->end();
for(node=it->begin();node!=endC;++node)
out << *node << " ";
out << "\n";
}
out.close();
return (0);
}
void depthFirst(int currentNode, int currentDepth,int father) {
vector<int>::iterator it,end = graph[currentNode].end();
depth[currentNode] = lowPoint[currentNode] = currentDepth;
for(it=graph[currentNode].begin();it!=end;++it)
// verificam sa nu se intoarca de unde a plecat
if(*it != father)
if(depth[*it]) // daca a fost vizitat
lowPoint[currentNode] = min(lowPoint[currentNode],depth[*it]);
else {
nodesStack.push(make_pair(currentNode,*it)); // punem muchia pe stiva
depthFirst(*it,currentDepth+1,currentNode); // exploram nodul
lowPoint[currentNode] = min(lowPoint[currentNode],lowPoint[*it]); // retinem minimul
// daca am identificat o componenta biconexa
// (am gasit un drum de intoarcere de la
// un urmas al nodului la acesta)
if(lowPoint[*it] >= depth[currentNode]) {
pair<int,int> currentEdge;
set<int> currentComponent;
// retinem si elimina din stiva toate muchiile
// pana la muchia (currentNode,*it) inclusiv
do {
currentEdge = nodesStack.top();
nodesStack.pop();
currentComponent.insert(currentEdge.from);
currentComponent.insert(currentEdge.to);
} while(currentEdge.from != currentNode && currentEdge.to != *it);
components.push_back(currentComponent);
}
}
}