Pagini recente » Profil mihnea.anghel | Cod sursa (job #2340738) | Cod sursa (job #2204174) | Cod sursa (job #136024) | Cod sursa (job #716742)
Cod sursa(job #716742)
// 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");
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)
if(*it != father)
if(depth[*it])
lowPoint[currentNode] = min(lowPoint[currentNode],depth[*it]);
else {
nodesStack.push(make_pair(currentNode,*it));
depthFirst(*it,currentDepth+1,currentNode);
lowPoint[currentNode] = min(lowPoint[currentNode],lowPoint[*it]);
if(lowPoint[*it] >= depth[currentNode]) {
pair<int,int> currentEdge;
set<int> currentComponent;
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);
}
}
}