Pagini recente » Cod sursa (job #1778573) | Cod sursa (job #2128148) | Cod sursa (job #2085743) | Cod sursa (job #1378948) | Cod sursa (job #2595500)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <deque>
#include <stack>
using namespace std;
ifstream fin;
ofstream fout;
vector <vector<int>> neighbours (100001);
bitset <100001> visited;
vector <int> level (100001);
vector <int> minimum_accessible (100001);
vector<vector<int>> biconnected_components;
bool searching_biconnected_component = false;
int nodes, edges, j, k;
void dfs_search(int where_to_start, int parent){
visited[where_to_start] = true;
level[where_to_start] = level[parent] + 1;
minimum_accessible[where_to_start] = level[where_to_start];
for (vector<int>::iterator it = neighbours[where_to_start].begin(); it != neighbours[where_to_start].end(); it++){
if (*it != parent){
if (!visited[*it]){
dfs_search(*it, where_to_start);
if (minimum_accessible[*it] < minimum_accessible[where_to_start])
minimum_accessible[where_to_start] = minimum_accessible[*it];
}
else if (level[*it] < minimum_accessible[where_to_start])
minimum_accessible[where_to_start] = level[*it];
}
}
}
void dfs_search_2(int where_to_start, stack <int> &biconnected_stack){
visited[where_to_start] = true;
biconnected_stack.push(where_to_start);
for (vector<int>::iterator it = neighbours[where_to_start].begin(); it != neighbours[where_to_start].end(); it++)
if(!visited[*it]){
if ((level[where_to_start] <= minimum_accessible[*it])){
stack<int> biconnected_stack_2;
biconnected_stack_2.push(where_to_start);
dfs_search_2(*it, biconnected_stack_2);
}else dfs_search_2(*it, biconnected_stack);
}
vector<int> aux;
for (; !biconnected_stack.empty(); biconnected_stack.pop())
aux.push_back(biconnected_stack.top());
if (aux.size() > 1)
biconnected_components.push_back(aux);
}
int main (void){
fin.open ("biconex.in");
fin>>nodes>>edges;
for (int i = 1; i<=edges; i++){
fin>>j>>k;
neighbours[j].push_back(k);
neighbours[k].push_back(j);
}
fin.close();
visited[1] = true;
level[1] = 1;
minimum_accessible[1] = 1;
for (vector<int>::iterator it = neighbours[1].begin(); it != neighbours[1].end(); it++)
if (!visited[*it]){
dfs_search(*it, 1);
}
for (int i=0; i<=nodes; i++)
visited[i] = false;
stack<int> biconnected_stack;
dfs_search_2(1, biconnected_stack);
fout.open("biconex.out");
fout<<biconnected_components.size()<<"\n";
for (vector<vector<int>>::iterator it1 = biconnected_components.begin(); it1 != biconnected_components.end(); it1++){
for (vector<int>::iterator it2 = it1->begin(); it2 != it1->end(); it2++)
fout<<*it2<<" ";
fout<<"\n";
}
fout.close();
return 0;
}