Pagini recente » Cod sursa (job #2154811) | Cod sursa (job #2302873) | Cod sursa (job #1910607) | Cod sursa (job #114397) | Cod sursa (job #2122433)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ofstream out("biconex.out");
ifstream in("biconex.in");
const int N_MAX = 100000;
vector<int> neighbours[1 + N_MAX], curcomp;
vector<vector<int>> components;
int n, depth[1 + N_MAX], height[1 + N_MAX], dad[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].push_back(y);
neighbours[y].push_back(x);
}
depth[1] = 1;
height[1] = 1;
}
void dfs(int node)
{
for(int m : neighbours[node])
{
if(dad[node] == m)
continue;
if(depth[m])
height[node] = min(height[node], height[m]);
else
{
dad[m] = node;
depth[m] = depth[node] + 1;
height[m] = depth[m];
dfs(m);
height[node] = min(height[node], height[m]);
}
}
}
void findcomponents(int node)
{
curcomp.push_back(node);
visited[node] = true;
for(int m : neighbours[node])
{
if(visited[m])
continue;
if(depth[node] <= height[m] & curcomp.size() != 1)
{
components.push_back(curcomp);
curcomp.clear();
curcomp.push_back(node);
}
findcomponents(m);
}
}
void print()
{
out << components.size() + 1 << "\n";
for(vector<int> m : components)
{
for(int r : m)
out << r << " ";
out << "\n";
}
for(int m : curcomp)
out << m << " ";
}
int main()
{
read();
dfs(1);
findcomponents(1);
print();
return 0;
}