Pagini recente » Cod sursa (job #165084) | Cod sursa (job #1604840) | Cod sursa (job #1786856) | Cod sursa (job #2002238) | Cod sursa (job #630640)
Cod sursa(job #630640)
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int NMAX = 100002;
int N , M;
VI G[NMAX] , dfn , low;
vector< VI > C;
stack<PII> S;
void read_data()
{
int x , y;
for(fin>>N>>M;M;M--)
{
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
dfn.resize(N+1,-1);
low.resize(N+1);
}
void cache_bc(const int x,const int y)
{
vector<int> con; int tx , ty;
do
{ tx = S.top().first , ty = S.top().second;
S.pop(); con.push_back(tx) , con.push_back(ty);
} while(x!=tx || y!=ty);
C.push_back(con);
}
void dfs(const int nod,const int fn,int num)
{
dfn[nod] = low[nod] = num;
for(VI::const_iterator it=G[nod].begin();it!=G[nod].end();++it)
if(fn!=*it)
{
if(dfn[*it]==-1)
{
S.push(make_pair(nod,*it));
dfs(*it,nod,num+1);
low[nod] = min(low[nod],low[*it]);
if(low[*it]>=dfn[nod]) cache_bc(nod,*it);
}
else
low[nod] = min(low[nod],dfn[*it]);
}
}
void print()
{
fout<<C.size()<<'\n';
for(size_t i=0;i<C.size();++i)
{
sort(C[i].begin(),C[i].end());
C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
for(size_t j=0;j<C[i].size();++j)
fout<<C[i][j]<<' ';
fout<<'\n';
}
}
int main()
{
read_data();
dfs(1,0,0);
print();
return 0;
}