Pagini recente » Cod sursa (job #1275055) | Cod sursa (job #1080555) | Cod sursa (job #1893816) | Cod sursa (job #2371949) | Cod sursa (job #670874)
Cod sursa(job #670874)
// 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];
vector<int> graph[MAXSIZE];
vector< set<int> > biConnectedComponent;
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 << biConnectedComponent.size() << "\n";
vector< set<int> >::iterator end = biConnectedComponent.end();
for(vector< set<int> >::iterator it=biConnectedComponent.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)
if(*it != father)
if(depth[*it])
lowPoint[currentNode] = min(lowPoint[currentNode],depth[*it]);
else {
edgesStack.push(make_pair(currentNode,*it));
depthFirst(*it,currentNode,currentDepth+1);
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);
biConnectedComponent.push_back(currentComponent);
}
}
}