原题链接:Leetcode 2368. 受限条件下可到达节点的数目
DFS
class Solution {
public:
vector<vector<int>> adj;
vector<int> visit;
map<int,int> mp;
int num=0;
void dfs(int now)
{
visit[now]=1;
num++;
for(auto x:adj[now])
{
if(!visit[x] && !mp[x]) dfs(x);
}
}
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
adj.resize(n);
visit.resize(n);
for(auto x:edges)
{
int a=x[0],b=x[1];
adj[a].push_back(b);
adj[b].push_back(a);
}
for(auto x:restricted) mp[x]=1;
dfs(0);
return num;
}
};
BFS
class Solution {
public:
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
vector<vector<int>> adj(n);
vector<int> visit(n);
map<int,int> mp;
int num=0;
for(auto x:edges)
{
int a=x[0],b=x[1];
adj[a].push_back(b);
adj[b].push_back(a);
}
for(auto x:restricted) mp[x]=1;
queue<int> q;
q.push(0);
while(!q.empty())
{
int x=q.front(); q.pop();
num++;
visit[x]=1;
for(auto y:adj[x])
{
if(!visit[y] && !mp[y]) q.push(y);
}
}
return num;
}
};
并查集
class Solution {
public:
map<int,int> fa;
int findfather(int x)
{
int a=x;
while(fa[x]!=x) x=fa[x];
while(fa[a]!=a)
{
int z=a;
a=fa[a];
fa[z]=x;
}
return x;
}
void Union(int x,int y)
{
int fx=findfather(x);
int fy=findfather(y);
if(fx!=fy)
{
if(fx<fy) fa[fy]=fx;
else fa[fx]=fy;
}
}
int reachableNodes(int n, vector<vector<int>>& edges, vector<int>& restricted) {
map<int,int> mp;
for(int i=0;i<n;i++) fa[i]=i;
for(auto x:restricted) mp[x]=1;
for(auto x:edges)
{
int a=x[0],b=x[1];
if(!mp[a] && !mp[b]) Union(a,b);
}
int num=0;
for(int i=0;i<n;i++)
{
if(mp[i]) continue;
if(fa[i]==0) num++;
else if(findfather(i)==0) num++;
}
return num;
}
};