#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>G[N];
int du[N],p[N];
priority_queue<int,vector<int>,greater<int>>Q;
bool bk[N];

int main()
{
    int n;scanf("%d",&n);
    for(int i=1,k;i<=n;i++)
    {
        scanf("%d",&k);
        for(int j=1,x;j<=k;j++)
        {
            scanf("%d",&x);
            G[i].push_back(x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        du[i]=G[i].size();
        if(du[i]==1) Q.push(i);
    }
    memset(bk,1,sizeof(bk));
    for(int i=1;i<=n-2;i++)
    {
        int x=Q.top();Q.pop();
        bk[x]=0;
        for(int y:G[x])
        {
            if(bk[y])
            {
                du[y]--;if(du[y]==1)Q.push(y);
                p[i]=y;
                break;
            }
        }
    }
    for(int i=1;i<=n-2;i++)printf("%d ",p[i]);
    return 0;
}

fxy代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>G[N];
int du[N],p[N];
priority_queue<int,vector<int>,greater<int>>Q;
bool bk[N];

int main() { int n;scanf("%d",&n); for(int i=1,k;i<=n;i++) { scanf("%d",&k); for(int j=1,x;j<=k;j++) { scanf("%d",&x); G[i].push_back(x); } } for(int i=1;i<=n;i++) { du[i]=G[i].size(); if(du[i]==1) Q.push(i); } memset(bk,1,sizeof(bk)); for(int i=1;i<=n-2;i++) { int x=Q.top();Q.pop(); bk[x]=0; for(int y:G[x]) { if(bk[y]) { du[y]--;if(du[y]==1)Q.push(y); p[i]=y; break; } } } for(int i=1;i<=n-2;i++)printf("%d ",p[i]); return 0; }</pre>