Pagini recente » Cod sursa (job #2154674) | Cod sursa (job #2594089) | Cod sursa (job #1655621) | Cod sursa (job #1451969) | Cod sursa (job #2595381)
#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <deque>
using namespace std;
ifstream fin;
ofstream fout;
vector <vector<int>> neighbours (100001);
bitset <100001> visited;
vector <int> level (100001);
vector <int> minimum_accessible (100001);
bitset <100001> articulation_points;
deque <pair<int, int>> biconnected_graph;
int nodes, edges, j, k, children_of_1;
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]){
biconnected_graph.push_back (pair<int, int> (where_to_start, *it));
dfs_search(*it, where_to_start);
if (minimum_accessible[*it] < minimum_accessible[where_to_start])
minimum_accessible[where_to_start] = minimum_accessible[*it];
if (level[where_to_start] <= minimum_accessible[*it])
articulation_points[where_to_start] = true;
}
else if (level[*it] < minimum_accessible[where_to_start])
minimum_accessible[where_to_start] = level[*it];
}
}
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]){
biconnected_graph.push_back (pair<int, int> (1, *it));
dfs_search(*it, 1);
children_of_1++;
}
if (children_of_1 > 1) articulation_points[1] = true;
int number_of_biconnected = 1;
for (deque<pair<int, int>>::iterator it = biconnected_graph.begin(); it != biconnected_graph.end(); it++){
if (articulation_points[it->first] && (level[it -> first] <= minimum_accessible[it -> second]))
number_of_biconnected++;
}
bool reset = true;
fout.open("biconex.out");
fout<<number_of_biconnected<<"\n";
for (; !biconnected_graph.empty(); biconnected_graph.pop_back()){
if (reset)
fout<<biconnected_graph.back().second<<" "<<biconnected_graph.back().first<<" ", reset = false;
else fout<<biconnected_graph.back().first<<" ";
if (articulation_points[biconnected_graph.back().first] && level[biconnected_graph.back().first] <= minimum_accessible[biconnected_graph.back().second])
fout<<"\n", reset = true;
}
fout.close();
return 0;
}