Cod sursa(job #1187281)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 18 mai 2014 01:50:27
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>

#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif

#include <cstdio>
#include <ctime>
#include <cmath>
#include <cstring>
#include <cstdlib>

using namespace std;

typedef long long int64;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

const int NMAX = 100010;

int N, M;

int where[NMAX];
vector<int> Gr[NMAX], GrT[NMAX], result[NMAX], discovered;
bitset<NMAX> used;

void DFP(const int &pos)
{
    int i, edge;
    used[pos] = true;
    for (i = 0; i < (int)Gr[pos].size(); ++i)
    {
        edge = Gr[pos][i];
        if (used[edge]) continue;
        DFP(edge);
    }
    discovered.push_back(pos);
}

int main()
{
    int x, y, i, j, edge, _edge, value = 0;
    queue<int> Q;

    fin >> N >> M;

    while(M--)
    {
        fin >> x >> y;
        Gr[x].push_back(y);
        GrT[y].push_back(x);
    }

    for (i = 1; i <= N; ++i)
    {
        if (used[i]) continue;
        DFP(i);
    }

    fill_n(where + 1, N, -1);

    for ( ; discovered.size(); discovered.pop_back())
    {
        if (where[discovered.back()] != -1) continue;
        where[discovered.back()] = value;
        Q.push(discovered.back());

        while(!Q.empty())
        {
            edge = Q.front(), Q.pop();

            for (j = 0; j < (int)GrT[edge].size(); ++j)
            {
                _edge = GrT[edge][j];
                if (where[_edge] != -1) continue;
                where[_edge] = value;
                Q.push(_edge);
            }
        }

        ++value;
    }

    for (i = 1; i <= N; ++i)
        result[where[i]].push_back(i);

    fout << value << '\n';

    for (i = 0; i < value; ++i)
    {
        for (j = 0; j < (int)result[i].size(); ++j)
            fout << result[i][j] << ' ';
        fout << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}