Cod sursa(job #1883781)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 18 februarie 2017 11:01:43
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 3.47 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;

stack<int> st;
int lrez = 0;
vector<int> rez[100001];
vector<int> g[100001];
int viz[100001], low[100001];
int n, m;

void dfs(int nod, int tnod)
{
	viz[nod] = viz[tnod] + 1;
	low[nod] = viz[nod];
	st.push(nod);
	for (int i = 0; i < g[nod].size(); i++)
	{
		if (g[nod][i] != tnod)
		{
			if (!viz[g[nod][i]])
			{
				dfs(g[nod][i], nod);
				low[nod] = min(low[nod], low[g[nod][i]]);

				if (viz[nod] <= low[g[nod][i]])
				{
				    while(!st.empty() && st.top() != g[nod][i])
                    {
                        rez[lrez].push_back(st.top());
                        st.pop();
                    }
                    rez[lrez].push_back(st.top());
                    st.pop();
                    rez[lrez].push_back(nod);
                    /*
					while (lst > 0 && st[lst - 1] != g[nod][i])
					{
						lst--;
						rez[lrez].push_back(st[lst]);
					}
					lst--;
					rez[lrez].push_back(st[lst]);
					rez[lrez].push_back(nod);*/
					sort(rez[lrez].begin(), rez[lrez].end());
					lrez++;
				}
			}
			else low[nod] = min(low[nod], low[g[nod][i]]);
		}
	}
}

struct Pas { int nod, tnod; } pas[100001];
char post[100001];
int pc;

int mdfs(int nod, int tnod)
{
    pc = 0;
    pas[0].nod = nod;
    pas[0].tnod = tnod;
    viz[nod] = viz[tnod] + 1;
    low[nod] = viz[nod];
    st.push(nod);
    while(pc >= 0)
    {
        nod = pas[pc].nod;
        tnod = pas[pc].tnod;
        if(post[pc])
        {
            post[pc] = 0;
            int onod = pas[pc + 1].nod;
            low[nod] = min(low[nod], low[onod]);

            if (viz[nod] <= low[onod])
            {
                while(!st.empty() && st.top() != onod)
                {
                    int t = st.top();
                    rez[lrez].push_back(st.top());
                    st.pop();
                }
                rez[lrez].push_back(st.top());
                st.pop();
                rez[lrez].push_back(nod);
                sort(rez[lrez].begin(), rez[lrez].end());
                lrez++;
            }
        }
        else if(g[nod].size())
        {
            for(int i = g[nod].size() - 1; i >= 0; i--)
            {
                if(g[nod][i] != tnod)
                {
                    if (!viz[g[nod][i]])
                    {
                        post[pc] = 1;
                        pc++;
                        pas[pc].nod = g[nod][i];
                        pas[pc].tnod = nod;
                        viz[g[nod][i]] = viz[nod] + 1;
                        low[g[nod][i]] = viz[g[nod][i]];
                        st.push(g[nod][i]);
                        g[nod].pop_back();
                        break;
                    }
                    else low[nod] = min(low[nod], low[g[nod][i]]);
                }
                g[nod].pop_back();
            }
        }
        else pc--;
    }
}

int main()
{
	int a, b;
	freopen("biconex.in", "r", stdin);
	freopen("biconex.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!viz[i])
			mdfs(i, 0);
	}
	printf("%d\n", lrez);
	for (int i = 0; i < lrez; i++)
	{
		for (int j = 0; j < rez[i].size(); j++)
		{
			printf("%d ", rez[i][j]);
		}
		printf("\n");
	}
	return 0;
}