Cod sursa(job #2526815)

Utilizator VanaMarcVana Marc VanaMarc Data 19 ianuarie 2020 11:36:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fi("ctc.in");
ofstream fo("ctc.out");
vector <int> A[100001];
vector <int> T[100001];
vector <int> C[100001];
int n,m;
int VIZ[100001];
stack <int> s;
int nrc;

void df(int v)
{
    vector <int> :: iterator it;
    VIZ[v]=1;
    for (it=A[v].begin();it!=A[v].end();it++)
    {
        int w;
        w=(*it);
        if (VIZ[w]==0)
            df(w);
    }
    s.push(v);
}

void dft(int v)
{
    vector <int> :: iterator it;
    VIZ[v]=1;
    C[nrc].push_back(v);
    for (it=T[v].begin();it!=T[v].end();it++)
    {
        int w;
        w=(*it);
        if (VIZ[w]==0)
            dft(w);
    }
}

int main()
{
    fi>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        fi>>a>>b;
        A[a].push_back(b);
        T[b].push_back(a);
    }
    /// algoritmul Kosaraju-Sharir
    /// se depun varfurile grafului in s, dupa finishing time
    for (int i=1;i<=n;i++)
        if (VIZ[i]==0)
            df(i);
    /// se fac traversari df in graful transpus
    /// considerand varfurile in ordinea extragerii din s
    for (int i=1;i<=n;i++)
        VIZ[i]=0;
    nrc=0;
    while (!s.empty())
    {
        int v;
        v=s.top();
        s.pop();
        if (VIZ[v]==0)
        {
            nrc++;
            dft(v);
        }
    }
    fo<<nrc<<"\n";
    for (int i=1;i<=nrc;i++)
    {
        vector <int> :: iterator it;
        for (it=C[i].begin();it!=C[i].end();it++)
            fo<<(*it)<<" ";
        fo<<"\n";
    }
    fi.close();
    fo.close();
    return 0;
}