[CCF 201709-4] Communication network (Warshall 65 points)

思想

Use the warshall algorithm to pass the closure, then traverse the adjacency matrix to calculate several departments can access N departments

O (n^3), obviously timed out, but the code is short, and the water score is still very good.

Warshall has two versions, the first version is 60 points, the second version is 65 points

#include <iostream>
Using namespace std;

Int n,m,a,b;
Bool adj[1001][1001];

Int main()
{
Cin>>n>>m;
For(int i=1; i<=n; ++i)
Adj[i][i] = 1;
While(m--)
{
Cin>>a>>b;
Adj[a][b] = 1;
}

//	version 1: 
// for(int k=1; k<=n; ++k)
// for(int i=1; i<=n; ++i)
// for(int j=1; j<=n; ++j)
// adj[i][j] = adj[i][j] | (adj[i][k] & adj[k][j]);

// Version 2:
For(int j=1; j<=n; j++)
For(int i=1; i<=n; i++)
{
If(adj[i][j])
For(int k=1; k<=n; k++)
Adj[i][k] |= adj[j][k];
}

Int cnt = 0;
Bool flag = 1;
For(int i=1; i<=n; ++i)
{
Flag = 1;
For(int j=1; j<=n; ++j)
{
If(!((adj[i][j] || adj[j][i]))))
{
Flag = 0;
Break;
}
}
If(flag) ++cnt;
}

Cout<<cnt;
Return 0;
}