Pagini recente » Cod sursa (job #708801) | Cod sursa (job #2657823) | Cod sursa (job #2174478) | Cod sursa (job #1974106) | Cod sursa (job #1414102)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int N, M, x, y, dad[100005], low[100005], found[100005], order;
vector < int > G[100005], Part;
vector< vector<int> > BCC;
vector < pair <int, int> > st, CE;
template <class T>
inline void elimdupli(vector< T > &v)
{
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
void getbcc(pair<int, int> M)
{
vector<int> newbcc; newbcc.clear();
pair < int, int > E;
do
{
E=st.back(); st.pop_back();
newbcc.push_back(E.first); newbcc.push_back(E.second);
} while (E!=M);
elimdupli(newbcc);
BCC.push_back(newbcc);
}
void dfs(int nod)
{
int sons=0;
low[nod]=found[nod]=++order;
vector<int>::iterator it=G[nod].begin();
for (; it!=G[nod].end(); ++it)
if (!dad[*it])
{
++sons; dad[*it]=nod; st.push_back(make_pair(nod, *it));
dfs(*it); low[nod]=min(low[nod], low[*it]);
if (low[*it]>=found[nod])
getbcc(make_pair(nod, *it));
if (low[*it]>=found[nod] && dad[nod]!=nod)
Part.push_back(nod);
if (low[*it]>found[nod])
CE.push_back(make_pair(nod, *it));
}
else if (dad[nod]!=*it)
low[nod]=min(low[nod], found[*it]);
if (dad[nod]==nod && sons>1)
Part.push_back(nod);
}
void solve()
{
dad[1]=1; dfs(1);
elimdupli(Part);
elimdupli(CE);
}
void printbcc()
{
g<<BCC.size()<<'\n';
for (int i=0; i<(int)BCC.size(); ++i)
{
for (int j=0; j<(int)BCC[i].size(); ++j)
g<<BCC[i][j]<<' '; g<<'\n';
}
}
int main()
{
f>>N>>M;
for (int i=1; i<=M; ++i)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
solve();
printbcc();
return 0;
}