Cod sursa(job #1251410)

Utilizator taigi100Cazacu Robert taigi100 Data 29 octombrie 2014 13:51:44
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.75 kb
/*
    Keep It Simple!
*/

#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<bitset>

#define pb(a) push_back(a)

using namespace std;

const int Max_N=606;

int N,M,CTC_Realzz[Max_N],Final_resault;
vector<int> G[Max_N],G_t[Max_N],topo,ctc,G_ctc[Max_N];
bool viz[Max_N];
bitset<Max_N> Direct_Roads[Max_N],InDirect_Roads[Max_N];

void Read_Input()
{
    ifstream f("graf2.in");

    f >> N >> M;

    int x,y;
    for(int i=0; i<M; ++i)
    {
        f >> x >> y;
        G[x].pb(y);
        G_t[y].pb(x);
    }

    f.close();
}

void First_DFS(int node)
{
    viz[node] = true;

    for(int i=0; i<G[node].size(); ++i)
    {
        int vecin = G[node][i];
        if(!viz[vecin])
            First_DFS(vecin);
    }
    topo.push_back(node);
}

void Second_DFS(int node)
{
    viz[node] = false;
    for(int i=0; i<G_t[node].size(); ++i)
    {
        int vecin = G_t[node][i];
        if(viz[vecin])
            Second_DFS(vecin);
    }
    ++ctc[ctc.size()-1];
    CTC_Realzz[node] = ctc.size();
}

void Kruskal()
{
    memset(viz,0,Max_N);

    for(int i=1; i<=N; ++i)
        if(!viz[i])
            First_DFS(i);

    reverse(topo.begin(),topo.end());

    for(int i=0; i<N; i++)
    {
        int node = topo[i];
            if(viz[node])
            {
                ctc.pb(0);
                Second_DFS(node);
            }
    }
}

void Compute_Comprimated_Graph()
{
    for(int i=1; i<=N; ++i)
        for(int j=0; j<G[i].size(); ++j)
        {
            int vecin = G[i][j];
            if(CTC_Realzz[i] != CTC_Realzz[vecin] && Direct_Roads[CTC_Realzz[i]][CTC_Realzz[vecin]] == false)
            {
                G_ctc[CTC_Realzz[i]].pb(CTC_Realzz[vecin]);
                Direct_Roads[CTC_Realzz[i]][CTC_Realzz[vecin]] = true;
            }
        }

    for(int i=0; i<ctc.size(); ++i)
    {
        for(int j=0; j<G_ctc[i].size(); ++j)
        {
            int eu = i;
            int vecin = G_ctc[eu][j];
            InDirect_Roads[eu] |= (Direct_Roads[vecin] | InDirect_Roads[vecin]);
        }
    }

    for(int i=0; i<ctc.size(); ++i)
    {
        int eu = i;
        InDirect_Roads[eu].flip();
        Direct_Roads[eu] &= InDirect_Roads[eu];
        Final_resault += Direct_Roads[eu].count();
    }
}

void Find_Resault()
{
    for(int i=0; i<ctc.size(); ++i)
        if(ctc[i] > 1)
            Final_resault += ctc[i];
}

void Print_Resault()
{
    ofstream g("graf2.out");
    g << Final_resault;
    g.close();
}

void Solve()
{
    Read_Input();
    Kruskal();
    Compute_Comprimated_Graph();
    Find_Resault();
    Print_Resault();
}

int main()
{
    Solve();
    return 0;
}