Cod sursa(job #1320669)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 18 ianuarie 2015 12:09:20
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
 
const int lmax = 100005;
vector <int> vecini[lmax], sol[lmax];
stack < pair<int, int> >s;
int level[lmax], urm[lmax];
int n, m, nr;
 
void dfs(int nod, int nivel, int tata)
{
    vector <int>::iterator it;
 
    level[nod] = nivel;
 
    for (vector <int>::iterator it = vecini[nod].begin(); it!=vecini[nod].end(); it++)
	{
		if(*it!=tata)
		{
			if (!level[*it])
			{
				s.push(make_pair(nod,*it));
				urm[nod] = *it;
				dfs(*it, nivel + 1, nod);
 
				level[nod] = level[*it] < level[nod] ? level[*it] : level[nod];
 
				if (level[*it]>=nivel)
				{
					sol[++nr].push_back(nod);

                    while (s.top().first!=nod)
                    {
						sol[nr].push_back(s.top().second);
						s.pop();
                    }

                    sol[nr].push_back(s.top().second);
                    s.pop();
               }
			}
			else
				level[nod] = level[*it] < level[nod] ? level[*it] : level[nod];
		}
	}
}

int main()
{
	int player_unu=0;
 
    in>>n>>m;
 
    for(int i = 1; i<=m; i++)
    {
		int x, y; 
		in>>x>>y;
 
        vecini[x].push_back(y);
        vecini[y].push_back(x);
    }
 
    dfs(1,1,0);
 
    out<<nr<<'\n';
 
    for(int i = 1; i<=nr; i++)
    {
         for(vector <int>::iterator it=sol[i].begin();it!=sol[i].end();it++)
			out<<*it<<" ";
		 out<<'\n';
    }
 
    return player_unu;
}