首先这是一道强连通的题
1. 先缩点,然后用tarjan或korasaju都行
2. 缩点后,计算新图的入度
3. 判断所有入度为0的点 在不在 他可以联系的人内,如果不在这个人就永远无法被联系到,就是-1
贴代码
//
// Created by HuJJun on 2022/3/29.
//
#include <iostream>
#include <vector>
#include <cstring>
#include <bitset>
#include <stack>
#include <algorithm>
#include <map>
#include <set>
using namespace std;
const int N = 1000;
vector<int> edges[N + 1][2];
int n, m;
bitset<N + 1> vis;
stack<int> seq;
map<int, int> mp;
set<int> inner[N+1];
int amt;
void dfs(int u) {
vis.set(u);
for (int v : edges[u][0])
if (!vis.test(v))
dfs(v);
seq.push(u);
}
void kosaraju(int u, int id) {
mp[u] = id;
inner[id].insert(u);
vis.reset(u);
for (int v : edges[u][1])
if (vis.test(v))
kosaraju(v, id);
}
void Kosaraju() {
vis.reset();
mp.clear();
amt = 0;
for (int i = 1; i <= n; i++)
if (!vis.test(i))
dfs(i);
while (!seq.empty()) {
int top = seq.top();
seq.pop();
if (vis.test(top))
kosaraju(top, ++amt);
}
}
int in[N+1];
void solver() {
memset(in,0,sizeof(in));
for(int u = 1 ; u <= n ; u++)
for(int v : edges[u][0])
if(mp[u]!=mp[v])
in[mp[v]]++;
vis.reset();
int cnt = 0;
bool flag = true; //能否传达上
for(int i = 1 ; i<= amt ; i++){ //可以通知的人
if(!in[i]) {//这个人是头
bool f = false;
for (int u : edges[0][0])
if(mp[u]==i){
f=true;
break;
}
if(f) { //将所有在的人压入
cnt++;
for (int v : inner[i])
if(!vis.test(v))
dfs(v);
}else {
flag = false;
break;
}
}
}
cout <<(flag?cnt:-1)<< endl;
}
int main() {
scanf("%d %d", &n, &m);
int u, v;
//可以通知的 人
for (int i = 0; i < m; ++i) {
scanf("%d", &v);
edges[0][0].push_back(v);
// edges[v][1].push_back(0);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &u);
for (int j = 0; j < u; ++j) {
scanf("%d", &v);
edges[i][0].push_back(v);
edges[v][1].push_back(i);
}
}
Kosaraju();
solver();
return 0;
}