Pagini recente » Cod sursa (job #28725) | Cod sursa (job #439024) | Cod sursa (job #2568315) | Cod sursa (job #2302164) | Cod sursa (job #1167273)
#include <fstream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N, M;
vector< vector<int> > G, Components;
vector<int> Level, LowLink;
stack< pair<int, int> > Stack;
void Read ()
{
f >> N >> M;
G.resize(N);
Level.resize(N, 0);
LowLink.resize(N, 0);
for (int i=0; i<M; i++)
{
int a, b;
f >> a >> b;
G[a-1].push_back(b-1);
G[b-1].push_back(a-1);
}
f.close();
}
void DF (int node, int father)
{
LowLink[node]=Level[node];
for (vector<int>::iterator it=G[node].begin(); it!=G[node].end(); ++it)
{
if (*it==father)
continue;
if (Level[*it]==0)
{
Level[*it]=Level[node]+1;
Stack.push(make_pair(node, *it));
DF(*it, node);
if (LowLink[*it]>=Level[node])
{
vector<int> Aux;
for (; !Stack.empty() && Stack.top()!=make_pair(node, *it); Stack.pop())
{
Aux.push_back(Stack.top().first);
Aux.push_back(Stack.top().second);
}
if (!Stack.empty() && Stack.top()==make_pair(node, *it))
{
Aux.push_back(Stack.top().first);
Aux.push_back(Stack.top().second);
Stack.pop();
}
sort(Aux.begin(), Aux.end());
Aux.resize(unique(Aux.begin(), Aux.end())-Aux.begin());
Components.push_back(Aux);
}
LowLink[node]=min(LowLink[node], LowLink[*it]);
}
else
LowLink[node]=min(LowLink[node], Level[*it]);
}
}
void Solve ()
{
for (int i=0; i<N; i++)
if (!Level[i])
{
Level[i]=1;
DF(i, -1);
}
}
void Print ()
{
g << Components.size() << '\n';
for (size_t i=0; i<Components.size(); i++)
{
for (vector<int>::iterator it=Components[i].begin(); it!=Components[i].end(); ++it)
g << (*it)+1 << ' ';
g << '\n';
}
g.close();
}
int main ()
{
Read();
Solve();
Print();
return 0;
}