Pagini recente » Cod sursa (job #2491021) | Cod sursa (job #2784515) | Cod sursa (job #1938020) | Cod sursa (job #2907723) | Cod sursa (job #724215)
Cod sursa(job #724215)
// 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");
int nodes,edges;
int depth[MAXSIZE],lowPoint[MAXSIZE];
stack< pair<int,int> > edgesStack;
vector< set<int> > components;
vector<int> graph[MAXSIZE];
void depthFirst(int currentNode,int currentDepth,int father);
int main() {
in >> nodes >> edges;
pair<int,int> currentEdge;
for(int i=1;i<=edges;i++) {
in >> currentEdge.from >> currentEdge.to;
graph[currentEdge.from].push_back(currentEdge.to);
graph[currentEdge.to].push_back(currentEdge.from);
}
in.close();
depthFirst(1,1,-1);
out << components.size() << "\n";
for(unsigned int i=0;i<components.size();i++) {
set<int>::iterator it,end = components[i].end();
for(it=components[i].begin();it!=end;++it)
out << *it << " ";
out << "\n";
}
out.close();
return (0);
}
void depthFirst(int currentNode,int currentDepth,int father) {
depth[currentNode] = lowPoint[currentNode] = currentDepth;
vector<int>::iterator it,end = graph[currentNode].end();
for(it=graph[currentNode].begin();it!=end;++it)
if(*it != father)
if(depth[*it])
lowPoint[currentNode] = min(lowPoint[currentNode],depth[*it]);
else {
edgesStack.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 = edgesStack.top();
edgesStack.pop();
currentComponent.insert(currentEdge.from);
currentComponent.insert(currentEdge.to);
} while(currentEdge.from != currentNode && currentEdge.to != *it);
components.push_back(currentComponent);
}
}
}