Cod sursa(job #2955967)

Utilizator rARES_4Popa Rares rARES_4 Data 18 decembrie 2022 13:32:01
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <bitset>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> adiacenta[100001];
vector<int> rasp[100001];
stack<int>st;
int n,m,cnt,comp;
bitset<100001> viz,in_stack;
int low_link[100001],indice[100001];

void DFS(int nod)
{
    low_link[nod] = ++cnt;
    indice[nod] = cnt;
    viz[nod] = 1;
    st.push(nod);
    in_stack[nod]=1;
    for(auto x:adiacenta[nod])
    {
        if(!viz[x])
        {
            DFS(x);
        }
    }
    for(auto x:adiacenta[nod])
    {
        if(viz[x] && in_stack[x])
        {
            low_link[nod] = min(low_link[nod],low_link[x]);
        }
    }
    if(low_link[nod] == indice[nod])
    {
        comp++;
        while(!st.empty())
        {
            int curent = st.top();
            st.pop();
            in_stack[curent] = 0;
            rasp[comp].push_back(curent);
            if(low_link[curent] ==indice[curent])
                {
                    break;
                }
        }
    }

}
int main()
{
    f >> n >> m;
    for(int i = 1;i<=m;i++)
    {
        int x,y;
        f >> x >> y;
        adiacenta[x].push_back(y);
    }

    for(int i = 1;i<=n;i++)
    {
        if(!viz[i])
        {
        }
    }
    g << comp<< '\n';

}