Pagini recente » Cod sursa (job #271862) | Cod sursa (job #2811917) | Cod sursa (job #2230052) | Cod sursa (job #3273766) | Cod sursa (job #1890534)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
void DFS (unsigned int node, unsigned int father);
unsigned int N, M;
unsigned int x, y;
vector <unsigned int> G[100001];
stack < pair <unsigned int, unsigned int> > ST;
unsigned int idx[100001], mini[100001];
unsigned int i, j;
unsigned int solution;
vector <unsigned int> sol[100001];
int main ()
{
fin >> N >> M;
for(i=1; i<=M; i++)
{
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
DFS(1,0);
fout << solution << '\n';
for (i=1; i<=solution; i++)
{
for (j=0; j<sol[i].size(); j++)
fout << sol[i][j] << ' ';
fout << '\n';
}
return 0;
}
void DFS (unsigned int node, unsigned int father)
{
unsigned int i;
idx[node] = idx[father] + 1;
mini[node] = idx[father] + 1;
for (i=0; i<G[node].size(); i++)
if (G[node][i] != father)
{
if (!idx[G[node][i]])
{
ST.push(make_pair(node,G[node][i]));
DFS(G[node][i],node);
if (mini[G[node][i]] >= idx[node])
{
solution++;
do
{
x = ST.top().first;
y = ST.top().second;
ST.pop();
sol[solution].push_back(y);
} while (x != node && y != G[node][i]);
sol[solution].push_back(node);
}
}
mini[node] = min(mini[node],mini[G[node][i]]);
}
}