Pagini recente » Cod sursa (job #251861) | Cod sursa (job #1881905) | Cod sursa (job #3038471) | Cod sursa (job #857213) | Cod sursa (job #1251410)
/*
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;
}