Mai intai trebuie sa te autentifici.

Cod sursa(job #2568876)

Utilizator E1goBack Andrei-Gheorghe E1go Data 4 martie 2020 10:16:34
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
using namespace std;

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

vector < vector <int> > G, Gt;
vector <int> s, viz;
int nr;

void Dfs2(int x)
{
    viz[x] = nr;
    for(int i=0; i<Gt[x].size(); i++)
        if(viz[ Gt[x][i] ] == -1)
            Dfs2(Gt[x][i]);
}

void Dfs1(int x)
{
    viz[x] = -1;
    for(int i=0; i<G[x].size(); i++)
        if(viz[ G[x][i] ] == 0)
            Dfs1(G[x][i]);
    s.push_back(x);
}

int main()
{
    int n, m, x, y;
    fin>>n>>m;
    G.resize(n+1); Gt.resize(n+1); viz.resize(n+1);
    while(m)
    {
        fin>>x>>y;
        G[x].push_back(y);
        Gt[y].push_back(x);
        m--;
    }

    for(int i=1; i<=n; i++)
     if(viz[i] == 0)
      Dfs1(i);

    for(int i=s.size()-1; i>=0; i--)
     if(viz[s[i]] == -1)
        {
            nr++;
            Dfs2(s[i]);
        }
    fout<<nr<<"\n";
    for(int i=1; i<=nr; i++)
    {
      for(int j=1; j<=n; j++)
            if(viz[j] == i)
             fout<<j<<" ";
      fout<<"\n";
    }
    return 0;
}