Cod sursa(job #754456)

Utilizator ioibojanBojan Aleksovski ioibojan Data 2 iunie 2012 02:12:53
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.26 kb
#include <cstdio>
#include <vector>
#include <set>
#include <cstring>
#include <stack>
#include <algorithm>
using namespace std;

vector<int> v[100001];
vector<int> component[100001];

int counter = -1;

int depth[100001], low[100001];

stack<int> s;

	inline void retrieve_component(int where, int next)
	{
		counter++;

		while (true)
		{
			int y = s.top(); s.pop();
			int x = s.top(); s.pop();

            component[counter].push_back(x);
            component[counter].push_back(y);

			if (x == where && y == next)
				break;
		}
	}

	void dfs(int where, int parent, int d)
	{
		depth[where] = d;
		low[where] = d;

		for (int nn=0; nn<(int)v[where].size(); nn++)
		{
		    int next = v[where][nn];

			if (next == parent)
				continue;

			if (depth[next] >= 0)
			{
				low[where] = min(low[where], depth[next]);

				if (depth[next] < depth[where])
				{
                    s.push(where);
                    s.push(next);
				}
			} else
			{
				s.push(where);
                s.push(next);

				dfs(next, where, depth[where] + 1);
				low[where] =min(low[where], low[next]);

				if (low[next] >= depth[where])
				{

					retrieve_component(where, next);
				}
			}
		}
	}


int main()
{
    FILE *input = fopen("biconex.in", "r");
    FILE *output = fopen("biconex.out", "w");


    int n, m;
    fscanf(input, "%d %d", &n, &m);

    for (int i=0; i<m; i++)
    {
        int a, b;
        fscanf(input, "%d %d", &a, &b);
        a--; b--;

        v[a].push_back(b);
        v[b].push_back(a);
    }

    memset(depth, -1, sizeof(depth));
    memset(low, -1, sizeof(low));

    dfs(0, -1, 0);

    fprintf(output, "%d\n", counter+1);

    for (int zz=0; zz<counter+1; zz++)
    {
        sort(component[zz].begin(), component[zz].end());
        component[zz].erase(unique(component[zz].begin(), component[zz].end()), component[zz].end());

        for (int kk=0; kk<(int)component[zz].size(); kk++)
        {
            if (kk == 0)
                fprintf(output, "%d", (component[zz][kk]+1));
            else
                fprintf(output, " %d", (component[zz][kk]+1));
        }

        fprintf(output, "\n");
    }

    fclose(input);
    fclose(output);
    return 0;
}