Pagini recente » Cod sursa (job #358939) | Cod sursa (job #2133369) | Cod sursa (job #1423538) | Cod sursa (job #1099634) | Cod sursa (job #547470)
Cod sursa(job #547470)
// http://infoarena.ro/problema/biconex
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
#define maxSize 100002
#define from first
#define to second
ifstream in("biconex.in");
ofstream out("biconex.out");
int nodes,edges,nrConnected;
int depth[maxSize];
int low[maxSize];
vector<int> biConnectedComponents[maxSize];
vector<int> graph[maxSize];
stack< pair<int,int> > edgeStack;
void depthFirst(int currentNode,int father,int currentDepth);
void saveEdges(int from,int to);
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);
}
depthFirst(1,-1,1);
out << nrConnected << "\n";
vector<int>::iterator it,end;
for(int i=1;i<=nrConnected;i++) {
sort(biConnectedComponents[i].begin(),biConnectedComponents[i].end());
int previous = 0;
end = biConnectedComponents[i].end();
for(it=biConnectedComponents[i].begin();it!=end;++it)
if(*it != previous)
out << (previous = *it) << " ";
out << "\n";
}
in.close();
out.close();
return (0);
}
void depthFirst(int currentNode,int father,int currentDepth) {
vector<int>::iterator it,end;
end = graph[currentNode].end();
depth[currentNode] = low[currentNode] = currentDepth;
for(it=graph[currentNode].begin();it!=end;++it) {
if(*it != father)
if(depth[*it])
low[currentNode] = min(low[currentNode],depth[*it]);
else {
edgeStack.push(make_pair(currentNode,*it));
depthFirst(*it,currentNode,currentDepth+1);
low[currentNode] = min(low[currentNode],low[*it]);
if(low[*it] >= depth[currentNode])
saveEdges(currentNode,*it);
}
}
}
void saveEdges(int from,int to) {
int currentFrom,currentTo;
nrConnected++;
do {
currentFrom = edgeStack.top().from;
currentTo = edgeStack.top().to;
edgeStack.pop();
biConnectedComponents[nrConnected].push_back(currentFrom);
biConnectedComponents[nrConnected].push_back(currentTo);
} while(currentFrom != from || currentTo != to);
}