Cod sursa(job #1834328)

Utilizator tziplea_stefanTiplea Stefan tziplea_stefan Data 24 decembrie 2016 13:25:12
Problema Componente tare conexe Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <vector>
#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;
int gasit[VAL];
bool ok[VAL], ok2[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[], int pas)
{
    vector<int> :: iterator it;
    gas[x]=true;
    if (pas==2 && ok[x]==true)
      gasit[x]=K;
    for (it=Graf[x].begin(); it!=Graf[x].end(); it++)
      if (gas[*it]==false)
        dfs(*it, Graf, gas, pas);
}

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]==0)
        {
            ++K;
            gasit[i]=K;
            comp[K].push_back(i);
            ok[i]=true;
            dfs(i, G, ok, 1);
            ok2[i]=true;
            dfs(i, Ginv, ok2, 2);
            memset(ok, false, sizeof(ok));
            memset(ok2, false, sizeof(ok2));
        }
        else
          comp[gasit[i]].push_back(i);
    }
    fout << K << '\n';
    for (i=1; i<=K; i++)
    {
        for (it=comp[i].begin(); it!=comp[i].end(); it++)
          fout << *it << " ";
        fout << '\n';
    }
    fin.close();
    fout.close();
    return 0;
}