讨论 / BFS大法好
sz136380243 2017-03-05 03:51:28
点我顶贴 收藏 删除
#include <iostream>

#include <queue>

using namespace std;

#define MAXNUM 1001

int n, m;

int Reachable[MAXNUM][MAXNUM];

int x[MAXNUM], y[MAXNUM];

int visited[MAXNUM], prev[MAXNUM];

int main()

{

int i, j, sum = 0;

queue<int> vec;

cin >> n;

for( i = 1; i <= n; i++ ){

x[i] = y[i] = -1;

visited[i] = -1;

for( j = 1; j <= n; j++ )

Reachable[i][j] = 1;

}

for( i = 1; i <= n; i++ ){

int num, people;

cin >> num;

for( j = 1; j <= num; j++ ){

cin >> people;

Reachable[i][people] = 0;

}

}

for( i = 1; i <= n; i++ ){

if( x[i] == -1 ){

bool flag = false;

while( !vec.empty() ) vec.pop();

vec.push(i);

prev[i] = -1;

while( !vec.empty() && !flag ){

int u = vec.front();

vec.pop();

for( int v = 1; v <= n; v++ ){

if( Reachable[u][v] && visited[v] != i ){

visited[v] = i;

vec.push( y[v] );

if( y[v] == -1 ){

flag = true;

int d = u, e = v;

while( d != -1 ){

int temp = x[d];

x[d] = e, y[e] = d;

e = temp, d = prev[d];

}

break;

}

else prev[y[v]] = u;

}

}

}

if( flag ) sum++;

}

}

cout << sum << endl;

return 0;

}

查看更多回复
提交回复