Pagini recente » Cod sursa (job #3215845) | Cod sursa (job #453027) | Cod sursa (job #127158) | Cod sursa (job #1616397) | Cod sursa (job #1577960)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
#define nmax 100001
using namespace std;
ifstream fi("biconex.in");
ofstream fo("biconex.out");
int n, m, a, b, numComp;
int Lev[nmax]; // Lev[i] = Nivelul pe care se afla nodul i in reprezentarea
// arborescenta a grafului
int Low[nmax]; // Low[i] = Nivelul minim care poate fi atins din nodul i
// mergand in jos pe arbore si folosind doar muchii
// de intoarcere pentru intoarcere
bool viz[nmax];
vector <int> G[nmax], Comp[nmax];
stack < pair <int, int> > S;
void newComp(int tata, int fiu)
{
int x = S.top().first;
int y = S.top().second;
S.pop();
while (tata != x && fiu != y)
{
Comp[numComp].push_back(x);
Comp[numComp].push_back(y);
x = S.top().first;
y = S.top().second;
S.pop();
}
Comp[numComp].push_back(x);
Comp[numComp].push_back(y);
}
void DFS(int tata)
{
viz[tata] = true;
for (int i = 0; i < G[tata].size(); i++)
{
int fiu = G[tata][i];
if (!viz[fiu])
{
S.push(make_pair(tata, fiu));
Lev[fiu] = Low[fiu] = Lev[tata] + 1;
DFS(fiu);
Low[tata] = min(Low[tata], Low[fiu]);
if (Low[fiu] >= Lev[tata])
{
numComp++;
newComp(tata, fiu);
}
}
else
{
Low[tata] = min(Low[tata], Lev[fiu]);
}
}
}
void write()
{
fo << numComp << "\n";
for (int i = 1; i <= numComp; i++)
{
sort(Comp[i].begin(), Comp[i].end());
Comp[i].push_back(0);
for (int j = 0; j < Comp[i].size() - 1; j++)
if (Comp[i][j] != Comp[i][j+1])
fo << Comp[i][j] << " ";
fo << "\n";
}
}
int main()
{
fi >> n >> m;
for (int i = 1; i <= m; i++)
{
fi >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
Lev[1] = Low[1] = 1;
DFS(1);
write();
fi.close();
fo.close();
return 0;
}