Cod sursa(job #1834314)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 24 decembrie 2016 13:07:26
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>
#define VAL 100005

using namespace std;

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

int N, M, i, j;
int x, y, K;
bool ok[VAL], ok2[VAL];
bool gasit[VAL];
vector<int> G[VAL];
vector<int> Ginv[VAL];
vector<int> comp[VAL];
vector<int> :: iterator it;

void dfs(int x, vector<int> Graf[], bool gas[])
{
    vector<int> :: iterator it;
    gas[x]=true;
    for (it=Graf[x].begin(); it!=Graf[x].end(); it++)
      if (gas[*it]==false)
        dfs(*it, Graf, gas);
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x >> y;
        G[x].push_back(y);
        Ginv[y].push_back(x);
    }
    for (i=1; i<=N; i++)
    {
        if (gasit[i]==false)
        {
            ++K;
            ok[i]=true;
            dfs(i, G, ok);
            ok2[i]=true;
            dfs(i, Ginv, ok2);
            for (j=1; j<=N; j++)
              if (ok[j]==true && ok2[j]==true)
                comp[K].push_back(j), gasit[j]=true;
            memset(ok, false, sizeof(ok));
            memset(ok2, false, sizeof(ok2));
        }
    }
    fout << K << '\n';
    for (i=1; i<=K; i++)
    {
        sort(comp[i].begin(), comp[i].end());
        for (it=comp[i].begin(); it!=comp[i].end(); it++)
          fout << *it << " ";
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}