Pagini recente » Cod sursa (job #2576478) | Cod sursa (job #1234455) | Cod sursa (job #2303633) | Cod sursa (job #166143) | Cod sursa (job #2122531)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ofstream out("biconex.out");
ifstream in("biconex.in");
const int N_MAX = 100000;
vector<int> neighbours[1 + N_MAX];
vector<vector<int>> components;
stack<pair<int, int>> dfs;
int n, depth[1 + N_MAX], height[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);
}
for(int i = 1; i <= n; i++)
depth[i] = -1;
}
void cache(int x, int y)
{
vector<int> curcomp;
int tx, ty;
do
{
tx = dfs.top().first;
ty = dfs.top().second;
dfs.pop();
curcomp.push_back(tx);
curcomp.push_back(ty);
}while(tx != x | ty != y);
components.push_back(curcomp);
}
void DFS(int node, int father, int Depth)
{
depth[node] = height[node] = Depth;
for(int m : neighbours[node])
{
if(m == father)
continue;
if(depth[m] != -1)
height[node] = min(height[node], depth[m]);
else
{
dfs.push(make_pair(node,m));
DFS(m, node, Depth+1);
height[node] = min(height[node], height[m]);
if(height[m] >= depth[node])
cache(node, m);
}
}
}
void print()
{
out << components.size() << "\n";
for(vector<int> m : components)
{
sort(m.begin(),m.end());
auto it = unique(m.begin(),m.end());
m.erase(it, m.end());
for(int r : m)
out << r << " ";
out << "\n";
}
}
int main()
{
read();
DFS(1, 0, 0);
print();
return 0;
}