Pagini recente » Cod sursa (job #2891921) | Cod sursa (job #3290206) | Cod sursa (job #388643) | Cod sursa (job #637675) | Cod sursa (job #2698914)
#include <fstream>
#include <stack>
#include <vector>
#include <set>
#define MAX_NODES 100005
#define MAX_EDGES 200005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
struct edge
{
int x, y;
bool viz;
int opposite(int nr)
{
if(x == nr)
return y;
return x;
}
void init(int x, int y)
{
this->x = x;
this->y = y;
}
} edges[MAX_EDGES];
vector<int> graf[MAX_NODES];
int n, m;
int lowlink[MAX_NODES];
int depth[MAX_NODES];
stack<int> S;
vector<set<int> >sol;
void read()
{
f>>n>>m;
int x, y;
for(int i = 0; i<m; i++)
{
f>>x>>y;
edges[i].init(x, y);
graf[x].push_back(i);
graf[y].push_back(i);
}
}
void popUntil(int targetEdge)
{
sol.push_back(set<int>());
while(!S.empty() && S.top() != targetEdge)
{
sol.back().insert(edges[S.top()].x);
sol.back().insert(edges[S.top()].y);
S.pop();
}
sol.back().insert(edges[S.top()].x);
sol.back().insert(edges[S.top()].y);
S.pop();
}
void dfs(int currNode, int dpt)
{
depth[currNode] = dpt;
lowlink[currNode] = dpt;
for(int i = 0; i<graf[currNode].size(); i++)
{
int nextNode = edges[graf[currNode][i]].opposite(currNode);
if(edges[graf[currNode][i]].viz)
continue;
edges[graf[currNode][i]].viz = true;
S.push(graf[currNode][i]);
if(depth[nextNode] == 0)
{
dfs(nextNode, dpt + 1);
if(lowlink[nextNode] >= depth[currNode])
{
popUntil(graf[currNode][i]);
}
}
if(depth[nextNode] > depth[currNode])
{
if(lowlink[nextNode] < lowlink[currNode])
lowlink[currNode] = lowlink[nextNode];
}
else
lowlink[currNode] = min(lowlink[currNode], depth[nextNode]);
}
}
void print()
{
g<<sol.size()<<"\n";
for(auto p : sol)
{
for(auto i : p)
{
g<<i<<" ";
}
g<<"\n";
}
}
int main()
{
read();
dfs(1, 1);
print();
return 0;
}