- Miku_兩個人焰火
- 2016-01-09 20:25:27 @
.................
###block code
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
vector<int>g[1500];
bool vis[1500];
bool b[1500];
void dfs(int k,int&x)
{
if(vis[k])return;
vis[k]=1;
x++;
for(int i=0;i<g[k].size();i++)
{
if(!b[g[k][i]])continue;
dfs(g[k][i],x);
}
}
int n,k;
int x,y;
int ans=0;
void chain(int k)
{
if(!b[k])return;
b[k]=0;
ans++;
for(int i=0;i<g[k].size();i++)
chain(g[k][i]);
}
void fire()
{
int M=0,e,p=1;
for(int i=1;i<=n;i++)
{
if(!b[i])continue;
e=0;
memset(vis,0,sizeof(vis));
dfs(i,e);
if(e>=M)
{
M=e;
p=i;
}
}
chain(p);
}
void solve()
{
while(k--)fire();
cout<<ans;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>k;
memset(b,1,sizeof(b));
for(int i=1;i<=n;i++)
{
cin>>x;
for(int j=1;j<=x;j++)
{
cin>>y;
g[y].push_back(i);
}
}
solve();
return 0;
}
1 条评论
-
Sky1231 (sky1231) LV 10 @ 2020-11-12 11:29:21
幫你整理一下上面的代碼
#include<iostream> #include<cstring> #include<vector> using namespace std; vector<int>g[1500]; bool vis[1500]; bool b[1500]; void dfs(int k,int&x) { if(vis[k]) return; vis[k]=1; x++; for(int i=0;i<g[k].size();i++) { if(!b[g[k][i]]) continue; dfs(g[k][i],x); } } int n,k; int x,y; int ans=0; void chain(int k) { if(!b[k]) return; b[k]=0; ans++; for(int i=0;i<g[k].size();i++) chain(g[k][i]); } void fire() { int M=0,e,p=1; for(int i=1;i<=n;i++) { if(!b[i]) continue; e=0; memset(vis,0,sizeof(vis)); dfs(i,e); if(e>=M) { M=e; p=i; } } chain(p); } void solve() { while(k--) fire(); cout<<ans; } int main() { ios::sync_with_stdio(false); cin>>n>>k; memset(b,1,sizeof(b)); for(int i=1;i<=n;i++) { cin>>x; for(int j=1;j<=x;j++) { cin>>y; g[y].push_back(i); } } solve(); return 0; }
- 1