.................
###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 条评论

  • @ 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

信息

ID
1692
难度
9
分类
图结构 | 强连通分量 点击显示
标签
(无)
递交数
1381
已通过
48
通过率
3%
被复制
2
上传者