Cod sursa(job #3203129)

Utilizator vlad414141414141Vlad Ionescu vlad414141414141 Data 13 februarie 2024 09:47:28
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

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

struct nod
{
    vector <int> v;
};

nod g[100041], g2[100041];
vector <int> viz1, viz2;
bool viz[100041], viz3[100041];
int n, m, x, y;

void read()
{
    fin >> n >> m;
    for (int i=0;i<m;++i)
    {
        fin >> x >> y;
        g[x].v.push_back(y);
        g2[y].v.push_back(x);
    }
}

void dfs1(int x)
{
  //  cout << x << " ";
    if (viz[x])
        return;
    else
    {
        viz[x]=true;
        viz1.push_back(x);
        for (int i=0;i<g[x].v.size();++i)
            dfs1(g[x].v[i]);
    }
}

void dfs2(int x)
{
    if (viz3[x])
        return;
    else
    {
        viz3[x]=true;
        viz2.push_back(x);
        for (int i=0;i<g2[x].v.size();++i)
            if (!viz3[g2[x].v[i]])
                dfs2(g2[x].v[i]);
    }
}

int main()
{
    read();
    int c=0;
    for (int i=1;i<=n;++i)
        if (!viz[i])
            dfs1(i);
    for (int i=1;i<=n;++i)
    {
        if (!viz3[i]){
            c++;
            dfs2(i);
            viz2.push_back(-1);
        }
    }
    fout << c << "\n";
    for (auto i:viz2)
    {
        if (i!=-1)
        fout << i << " ";
        else
            fout << "\n";
    }
    return 0;
}