Pagini recente » Cod sursa (job #2048344) | Cod sursa (job #125265) | Cod sursa (job #739519) | Cod sursa (job #1630467) | Cod sursa (job #2118099)
#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< vector<int> > BC;
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;
vector<int> currentBC;
do{
firstNodeFromStack = Stack.top().first;
secondNodeFromStack = Stack.top().second;
Stack.pop();
currentBC.push_back(firstNodeFromStack);
currentBC.push_back(secondNodeFromStack);
}while(firstNodeFromStack != firstNode and secondNodeFromStack != secondNode);
BC.push_back(currentBC);
}
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(){
vector< vector<int> >::iterator it1;
vector< int >::iterator it2;
fout << BC.size() << '\n';
for(it1 = BC.begin(); it1 != BC.end(); ++it1){
sort((*it1).begin(), (*it1).end());
(*it1).erase(unique((*it1).begin(), (*it1).end()), (*it1).end());
for(it2 = (*it1).begin(); it2 != (*it1).end(); ++it2)
fout << *it2 << ' ';
fout << '\n';
}
}
int main(){
read_data();
getBC(1, 1);
printBC();
}