Pagini recente » Cod sursa (job #1812909) | Cod sursa (job #2053735) | Cod sursa (job #1639384) | Cod sursa (job #2750045) | Cod sursa (job #2122487)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
ofstream out("biconex.out");
ifstream in("biconex.in");
struct Pair
{
int first, second;
};
const int N_MAX = 100050;
int neighbours[1 + N_MAX][1 + N_MAX/100];
vector<int> components[1 + N_MAX];
Pair dfs[2*N_MAX];
int n, k = 0, t= 0, depth[1 + N_MAX], height[1 + N_MAX], dad[1 + N_MAX], nrNb[1 + N_MAX];
bool visited[1 + N_MAX];
void read()
{
int m;
in >> n >> m;
for(int i = 0; i < m; i++)
{
int x, y;
in >> x >> y;
neighbours[x][nrNb[x]++] = y;
neighbours[y][nrNb[y]++] = x;
}
depth[1] = 1;
height[1] = 1;
}
void cache(int x, int y)
{
vector<int> curcomp;
int tx, ty;
do
{
tx = dfs[k].first;
ty = dfs[k].second;
k--;
curcomp.push_back(tx);
curcomp.push_back(ty);
}while(tx != x | ty != y);
components[t] = curcomp;
t++;
}
void DFS(int node)
{
for(int i = 0; i < nrNb[node]; i++)
{
int m = neighbours[node][i];
if(dad[node] == m)
continue;
if(depth[m])
height[node] = min(height[node], height[m]);
else
{
k++;
dfs[k] = {node,m};
dad[m] = node;
depth[m] = depth[node] + 1;
height[m] = depth[m];
DFS(m);
height[node] = min(height[node], height[m]);
if(height[m] >= depth[node])
cache(node, m);
}
}
}
void print()
{
out << t << "\n";
for(int m = 0; m < t; m++)
{
sort(components[m].begin(),components[m].end());
auto it = unique(components[m].begin(),components[m].end());
components[m].resize(distance(components[m].begin(),it));
for(int r : components[m])
out << r << " ";
out << "\n";
}
}
int main()
{
read();
DFS(1);
print();
return 0;
}