Pagini recente » Cod sursa (job #3275148) | Cod sursa (job #3164356) | Cod sursa (job #447702) | Cod sursa (job #1230082) | Cod sursa (job #1599315)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <utility>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
//Given limits
#define MAXN 100050
#define MAXM 200050
//Given variables
vector <int> edge[MAXN];
int N, M;
//Solution Variables
int depth_order[MAXN], first_from_x[MAXN];
vector < vector <int> > biconex_components;
stack < pair <int, int> > edges_work;
//tool functions
void initialize_array (int x[], int _size, int value)
{
for (int i = 0; i <= _size; ++i)
x[i] = value;
}
//SOLUTION / Complexity: O(N+M)
void push_solution (int x, int y)
{
vector <int> to_push;
int temp_x, temp_y;
do
{
temp_x = edges_work.top().first;
temp_y = edges_work.top().second;
to_push.push_back(temp_x);
to_push.push_back(temp_y);
edges_work.pop();
}
while (temp_x != x || temp_y != y);
sort(to_push.begin(), to_push.end());
to_push.erase( unique( to_push.begin(), to_push.end() ), to_push.end() );
biconex_components.push_back(to_push);
}
void DFS (int node, int ancestor, int order)
{
depth_order[node] = first_from_x[node] = order;
for (int i = 0; i < edge[node].size(); ++i)
{
if (depth_order[edge[node][i]] == -1)
{
edges_work.push(make_pair(node, edge[node][i]));
DFS(edge[node][i], node, order+1);
first_from_x[node] = (first_from_x[node] < first_from_x[edge[node][i]]) ? (first_from_x[node]) : (first_from_x[edge[node][i]]);
if (first_from_x[edge[node][i]] >= depth_order[node])
push_solution(node, edge[node][i]);
}
else
first_from_x[node] = (first_from_x[node] < depth_order[edge[node][i]]) ? (first_from_x[node]) : (depth_order[edge[node][i]]);
}
}
int main()
{
fin >>N >>M;
for (int i = 0; i < M; ++i)
{
int x, y;
fin >>x >>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
initialize_array (depth_order, N+1, -1);
DFS (1, 0, 0);
fout <<biconex_components.size() <<'\n' ;
for (int i = 0; i < biconex_components.size(); ++i)
{
for (int j = 0; j < biconex_components[i].size(); ++j)
fout <<biconex_components[i][j] <<' ';
fout <<'\n';
}
return 0;
}