Pagini recente » Cod sursa (job #2637333) | Cod sursa (job #1707424) | Cod sursa (job #1929462) | Cod sursa (job #2496530) | Cod sursa (job #437245)
Cod sursa(job #437245)
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
#define pb push_back
#define mp make_pair
using namespace std;
const int NMAX = 100010;
int N, M;
vector<int> G[NMAX];
int dfn[NMAX], low[NMAX];
stack< pair<int, int> > st;
vector< vector<int> > biconex;
/*void write()
{
for(int i = 1 ; i <= M ; i++)
{
for(int k = 0 ; k < (int)G[i].size() ; k++)
printf("%d ", G[i][k]);
printf("\n");
}
for(int i = 1 ; i <= N ; i++)
printf("%d ", dfn[i]);
printf("\n");
for(int i = 1 ; i <= N ; i++)
printf("%d ", low[i]);
printf("\n\n\n");
}*/
void citire()
{
int x, y;
scanf("%d%d", &N, &M);
for(int i = 1 ; i <= M ; i++)
{
scanf("%d%d", &x, &y);
G[x].pb(y);
G[y].pb(x);
}
}
void introduc(int x, int y)
{
vector<int> cb;
pair<int, int> a;
do
{
a = st.top();
cb.pb(a.first);
cb.pb(a.second);
st.pop();
}while(x != a.first || y != a.second);
biconex.pb(cb);
}
void DFS(int nod, int tata, int nivel)
{
vector<int> :: iterator it;
dfn[nod] = low[nod] = nivel;
for(it = G[nod].begin() ; it != G[nod].end() ; ++it)
if(*it != tata)
if(dfn[*it] == -1)
{
st.push(mp(*it, nod));
DFS(*it, nod, nivel+1);
low[nod] = min(low[nod], low[*it]);
if(low[*it] >= dfn[nod])
introduc(*it, nod);
}
else
low[nod] = min(low[nod], dfn[*it]);//merge si min(low[nod], low[*it])
}
void scriere()
{
vector<int> :: iterator dim;
printf("%d\n",biconex.size());
sort(biconex.begin(), biconex.end());
for(int i = 0 ; i < (int)biconex.size() ; ++i)
{
sort(biconex[i].begin(), biconex[i].end());
dim = unique(biconex[i].begin(), biconex[i].end());
biconex[i].resize(dim - biconex[i].begin());
for(int k = 0 ; k < (int)biconex[i].size() ; ++k)
printf("%d ",biconex[i][k]);
printf("\n");
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
memset(dfn, -1, NMAX);
DFS(1, 0, 1);
//write();
scriere();
return 0;
}