Pagini recente » Cod sursa (job #2116088) | Cod sursa (job #575562) | Cod sursa (job #2408561) | Cod sursa (job #2990275) | Cod sursa (job #670886)
Cod sursa(job #670886)
// http://infoarena.ro/problema/biconex
#include <fstream>
#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 nodes,edges;
int depth[MAXSIZE],lowPoint[MAXSIZE];
vector<int> graph[MAXSIZE];
vector< set<int> > biConnectedComponents;
stack< pair<int,int> > edgesStack;
void depthFirst(int currentNode,int father,int currentDepth);
int main()
{
in >> nodes >> edges;
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 << biConnectedComponents.size() << "\n";
vector< set<int> >::iterator end = biConnectedComponents.end();
for(vector< set<int> >::iterator it=biConnectedComponents.begin();it!=end;++it)
{
set<int>::iterator endC = it->end();
for(set<int>::iterator node=it->begin();node!=endC;++node)
out << *node << " ";
out << "\n";
}
out.close();
return (0);
}
void depthFirst(int currentNode,int father,int currentDepth)
{
vector<int>::iterator end = graph[currentNode].end();
depth[currentNode] = lowPoint[currentNode] = currentDepth;
for(vector<int>::iterator it=graph[currentNode].begin();it!=end;++it)
// verificam sa nu se intorca de unde a plecat
if(*it != father)
// daca a fost vizitat
if(depth[*it])
lowPoint[currentNode] = min(lowPoint[currentNode],depth[*it]);
else {
// punem muchia pe stiva
edgesStack.push(make_pair(currentNode,*it));
// exploram nodul
depthFirst(*it,currentNode,currentDepth+1);
// retinem minimul
lowPoint[currentNode] = min(lowPoint[currentNode],lowPoint[*it]);
// 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 eliminam din stiva toate muchiile
// pana la muchia (currentNode,*it) inclusiv
do {
currentEdge = edgesStack.top();
edgesStack.pop();
currentComponent.insert(currentEdge.from);
currentComponent.insert(currentEdge.to);
} while(currentEdge.from != currentNode || currentEdge.to != *it);
biConnectedComponents.push_back(currentComponent);
}
}
}