Cod sursa(job #2844104)

Utilizator alessiamtr12Mitrica Alessia alessiamtr12 Data 3 februarie 2022 19:23:59
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include<vector>
#define NMAX 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,pluss[NMAX],minuss[NMAX],x,y;
vector<int>v[NMAX];
vector<int>w[NMAX];
int ctc[NMAX],nrc;
void dfs1(int x)
{
    pluss[x]=1;
    for(int i=0;i<v[x].size();i++)
    {
        int nod=v[x][i];
        if(pluss[nod]==0)
            dfs1(nod);
    }
}
void dfs2(int x)
{
    minuss[x]=1;
    for(int i=0;i<w[x].size();i++)
    {
        int nod=w[x][i];
        if(minuss[nod]==0)
            dfs2(nod);
    }
}
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        v[x].push_back(y);
        w[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
    {
        if(!ctc[i])
        {
            nrc++;
            dfs1(i);
            dfs2(i);
            for(int j=1;j<=n;j++)
            {
                if(pluss[j]&&minuss[j])
                    ctc[j]=nrc;
                pluss[j]=minuss[j]=0;
            }

        }
    }
    fout<<nrc<<"\n";
    for(int i=1;i<=nrc;i++)
    {
        for(int j=1;j<=n;j++)
            if(ctc[j]==i)
               fout<<j<<" ";
        fout<<"\n";
    }
    return 0;
}