Pagini recente » Cod sursa (job #1804138) | Cod sursa (job #1828555) | Cod sursa (job #2151) | Cod sursa (job #2543530) | Cod sursa (job #1907498)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
struct Graf { int level, returnLevel; vector<int> v; };
int n, index, nrComp;
Graf node[100002];
vector<int> comp[100002];
stack<int> myStack;
void GoVisit(int nod, int level)
{
node[nod].level = level;
node[nod].returnLevel = level;
myStack.push(nod);
for (vector<int>::iterator it = node[nod].v.begin(); it != node[nod].v.end(); it++)
if (!node[*it].level)
{
GoVisit(*it, level + 1);
if (node[*it].returnLevel < level)
node[nod].returnLevel = min(node[nod].returnLevel, node[*it].returnLevel);
else
{
nrComp++;
while (myStack.top() != nod)
{
comp[nrComp].push_back(myStack.top());
myStack.pop();
}
comp[nrComp].push_back(nod);
}
}
else if (node[*it].returnLevel < node[nod].returnLevel && node[*it].level != level - 1)
node[nod].returnLevel = node[*it].returnLevel;
}
int main()
{
int m, n1, n2;
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
fin >> n1 >> n2;
node[n1].v.push_back(n2);
node[n2].v.push_back(n1);
}
GoVisit(1, 1);
if (myStack.size() > 1)
{
nrComp++;
while (myStack.size())
{
comp[nrComp].push_back(myStack.top());
myStack.pop();
}
}
fout << nrComp << '\n';
for (int i = 1; i <= nrComp; i++)
{
sort(comp[i].begin(), comp[i].end());
for (int j = 0; j < comp[i].size(); j++)
fout << comp[i][j] << ' ';
fout << '\n';
}
return 0;
}