Cod sursa(job #3178317)

Utilizator tudorp_Pop Tudor tudorp_ Data 1 decembrie 2023 16:28:14
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.66 kb
#include <iostream>
#include <bits/stdc++.h>

#define pb push_back

using namespace std;

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

const int MAX = 26000;

//am dat define pb la push_back


int N,M,x,y,i,j,X;
vector<vector<int>> Graf(MAX);
vector<vector<int>> Graft(MAX);
queue<int> q;
int grad[MAX];
int nrc = 0;
int nodm;
bool viz[MAX], p[MAX], m[MAX]; //vectori de plus si minus;
int dis[MAX], Dad[MAX];
int ctc[MAX];

void clear_plus_minus()
{
    for(i=1;i<=N;i++)
    {
        m[i] = p[i] = 0;
    }
}

void citire()
{
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        Graf[x].pb(y);
        Graft[y].pb(x); //adaug in graful transpus
    }
}

void DFS(int nod)
{
    m[nod] = 1;
    for(auto vec:Graf[nod])
    {
        if(!m[vec])
        {
            m[vec] = 1;
            Dad[vec] = nod;
            DFS(vec);
        }
    }
}

void DFSt(int nod)
{
      p[nod] = 1;
      for(auto vec:Graft[nod])
      {
          if(!p[vec])
          {
              p[vec] = 1;
              Dad[vec] = nod;
              DFSt(vec);
          }
      }
}

int main()
{
    citire();
    for(i=1;i<=N;i++)
    {
        if(ctc[i]==0)
        {
            clear_plus_minus();
            nrc++;
            DFS(i);
            DFSt(i);
            for(int j=1;j<=N;j++)
            {
                if(m[j] && p[j])
                    ctc[j] = nrc;
            }
        }
    }
    fout<<nrc<<'\n';
    for(i=1;i<=nrc;i++)
    {
        for(int j=1;j<=N;j++)
        {
            if(ctc[j]==i)
                fout<<j<<" ";
        }
        fout<<'\n';
    }
}