P1726-上白泽慧音

逃离我推掉我的手 2023-06-01 08:55 11阅读 0赞

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 #define pb push_back
     4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
     5 #define _rep(i,a,b) for(int i = (a);i > (b);i --)
     6 #define INF 0x3f3f3f3f
     7 #define ll long long
     8 inline ll read()
     9 {
    10     ll ans = 0;
    11     char ch = getchar(), last = ' ';
    12     while(!isdigit(ch)) last = ch, ch = getchar();
    13     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    14     if(last == '-') ans = -ans;
    15     return ans;
    16 }
    17 inline void write(ll x)
    18 {
    19     if(x < 0) x = -x, putchar('-');
    20     if(x >= 10) write(x / 10);
    21     putchar(x % 10 + '0');
    22 }
    23 #define maxn 5003
    24 int n,m;
    25 vector<int> G[maxn];
    26 vector<int> rG[maxn];
    27 vector<int> vs;
    28 vector<int> ans[maxn];
    29 bool used[maxn];
    30 int V,E;
    31 int rnt = 0;
    32 void add_edge(int from,int to)
    33 {
    34     G[from].pb(to);
    35     rG[to].pb(from);
    36 }
    37 void dfs(int v)
    38 {
    39     used[v] = true;
    40     _for(i,0,G[v].size())
    41         if(!used[G[v][i]])
    42             dfs(G[v][i]);
    43     vs.pb(v);
    44 }
    45 void rdfs(int v,int k)
    46 {
    47     used[v] = true;
    48     ans[k].pb(v);
    49     _for(i,0,rG[v].size())
    50         if(!used[rG[v][i]])
    51             rdfs(rG[v][i],k);
    52 }
    53 void Kosaraju()
    54 {
    55     memset(used,0,sizeof(used));
    56     _for(v,1,V+1)
    57         if(!used[v])
    58             dfs(v);
    59     
    60     memset(used,0,sizeof(used));
    61     int k = 0;
    62     _rep(i,vs.size()-1,-1)
    63         if(!used[vs[i]])
    64         {
    65             rdfs(vs[i],k);
    66             rnt = max(rnt,(int)ans[k].size());
    67             k ++;
    68         }
    69 }
    70 int main()
    71 {
    72     V = read(),E = read();
    73     _for(i,1,E+1)
    74     {
    75         int a,b,t;
    76         a = read(),b = read(),t = read();
    77         add_edge(a,b);
    78         G[a].pb(b);
    79         if(2==t)
    80             add_edge(b,a);
    81     }
    82     Kosaraju();
    83     _for(i,0,5000)
    84         if(ans[i].size()==rnt)
    85         {
    86             sort(ans[i].begin(),ans[i].end());
    87             printf("%d\n",ans[i].size());
    88             _for(j,0,ans[i].size())
    89                 printf("%d ",ans[i][j]);
    90             break;
    91         }
    92     return 0;
    93 }

转载于:https://www.cnblogs.com/Asurudo/p/11535968.html