Pagini recente » Cod sursa (job #1922510) | Cod sursa (job #449683) | Cod sursa (job #1269513) | Cod sursa (job #1818811) | Cod sursa (job #2118100)
#include<fstream>
#include<list>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100005;
///BC = Biconnected Component
list<int> graph[NMAX];
stack< pair< int , int > > Stack;
vector<int> BC[NMAX];
int nodesCount, edgesCount, BCCount;
int level[NMAX], lowLevel[NMAX];
inline void read_data(){
fin >> nodesCount >> edgesCount;
int firstNode, secondNode;
while(edgesCount--){
fin >> firstNode >> secondNode;
graph[firstNode].push_back(secondNode);
graph[secondNode].push_back(firstNode);
}
}
inline void cache_newBC(int firstNode, int secondNode){
int firstNodeFromStack, secondNodeFromStack;
++BCCount;
do{
firstNodeFromStack = Stack.top().first;
secondNodeFromStack = Stack.top().second;
Stack.pop();
BC[BCCount].push_back(firstNodeFromStack);
BC[BCCount].push_back(secondNodeFromStack);
}while(firstNodeFromStack != firstNode and secondNodeFromStack != secondNode);
}
void getBC(int node, int currentLevel){
level[node] = lowLevel[node] = currentLevel;
list<int>::iterator it;
for(it = graph[node].begin(); it != graph[node].end(); ++it)
if(level[*it] == 0){
Stack.push({node, *it});
getBC(*it, currentLevel + 1);
lowLevel[node] = min(lowLevel[node], lowLevel[*it]);
if(level[node] <= lowLevel[*it])
cache_newBC(node, *it);
}
else
lowLevel[node] = min(lowLevel[node], level[*it]);
}
inline void printBC(){
int index;
vector< int >::iterator it;
fout << BCCount << '\n';
for(index = 1; index <= BCCount; ++index){
sort(BC[index].begin(), BC[index].end());
BC[index].erase(unique(BC[index].begin(), BC[index].end()), BC[index].end());
for(it = BC[index].begin(); it != BC[index].end(); ++it)
fout << *it << ' ';
fout << '\n';
}
}
int main(){
read_data();
getBC(1, 1);
printBC();
}