Language: C++

/*
ID:njbxgub1
PROB:Kosaraju算法(双dfs)缩点+DP
LANG:C++
*/
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . ___
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         ·e×?±￡óó       óà?TBUG
*/
/*
                 .::                                                       ,,         .:                    :,         :.
          :LuqL  5B@   :v             77L21F5F5F5F1F5S15Uv7,              :@B         0@U                  .B@        L@P
 B@B@@@B@B@B@@B  L@B   B@B@,          @BB2XSPSPkPXPkPXPF2B@B     .@B@B@B@B@@@B@B@B@B@@@B@B@B@B@B@ :@@@@BBMOB@BGM@B@BME@@@EMB@B@B@r
 ,Yi:  @B2       iB@     2@@@7        B@,                8Bq      vriii:.:0@@:ii::,:::B@B::iiii77 ,E1uJuJJ7GB@7LUk2ULvB@B7LjJjjSq:
       B@7        @B       i7         @B@B@B@B@B@B@B@B@B@B@k          @B  .BZ    u@.   :                   ,@N        7B2
0EqEqX2@B@1N0Z0ZSqB@qX0ZNPUYLSZ8      B@                 NBP          :@B       1@BMX0uj2EEZN15,    8@B@B@@@GGB@7 5@B@BOM@B@B@B.
@B@B@B@@@B@B@B@B@B@B@B@B@B@B@B@B      @B@B@B@B@B@B@B@B@B@B@q      @B@B@B@B@@@u S@B2qOOMOMM@BMB@L              @@7            B@.
       @Bv        @@v       .         B@:                k@v      :i;.,...q5::B@k            @Bi     8@@B@B@B@B@v  BB@B@B@B@@@B.
       B@L   .,7  0B@     SB@S   :5jj7vi::iiiii:..,:iii::;77LY25   B@     @B u@20B@B@B@B@N   @@:     B@       .:   B@        ::
 .:v28P@B@@@B@B@, ,@@   u@B@.    YB@B@ME0OB@B@@@B@BMB@B@BBOBB@B@.  L@@   OBS    B@:    JB@   @B.    v@BLuXP0qXvL: 1@B7ukXE00SYvL
@@@B@B@B@Z.        B@kLB@B:            7Ei      @@;                 @B:  B@     @B     .@O   B@      LO1i   , @B0  ;BX7.  ,..P@B
       @Bu         1B@B5     ::       :@B       B@@@B@B@@@B@B@      7@@ U@u     B@i,::.PB@   @B      .7OBGu   Z@v   rNBOFi   7B8
       B@5      7B@B@B@      B@B     i@B@7      @BN.::i:i:i:ii       17 @B      @B@B@B@MMY   B@          u@OBUMBi      :@BNBYv@F
       @B0  u@B@B@L  kB@;    @@;    0@B.J@@O:   B@i               ,:ii7@B@B@@@u SZ          i@B    LB@@@B@5Y, B@, 5@@@B@GFY: ZBu
 :5rr:5B@J  MBM:      iB@@k:@@@  ,NB@E    k@@B@B@B@qEZMMBM@MBB@Br @B@B@OY77:,      :MSUjuukB@Br    iBvUr.   .8@B  i5::r     YB@
 .B@B@BZ:                0B@B8   @BO         .:i:77uU5uFSkFkFXXq                    B@B@@@GU.         ,@B@B@BM:       B@B@B@B7
          .:7kq  ;@B,   ,                   @B.    i@M                .B@,      N@@       .BO       :,.            .:..
 LB@@@B@B@B@B@@  :B@,  EB@O,                B@i    U@@                 ,q@BX    1@B    ,q@B0:      ,B@B@B@B@B@B@1  @B@B@B@B@B@B@
  kri. M@@        @B:    u@B@J    @B@B@B@B@@@Bi    J@@@B@B@B@B@B   irrvi:u@BjLJ7@B@7YYLB@Bj::rir              @Bj            i@B
       EBO        @@:      :1     iiii:i::,:B@:    uB@.::i:i:iii   @B@qquvrLu1127rrUU5Uvrrv5q@B@.    .,iiiii::B@L   .,:iiiii:E@@
YLLvv7iB@Bi7YLYL7r@@ErLLL7r::iYU            @@i    Y@@             B@k      . .     ...       @B,    B@B@B@B@B@BF   @B@B@B@B@@@B
@@B@B@B@B@@@B@B@B@B@B@B@B@B@B@B@.           B@i    uB@             r7. ,B@MMMBMBMBMBMBMMG@B@  7v    r@M            LB8
       E@O        PBM       .     vB@B@B@@@B@Bi    J@B@B@B@B@@@7       .@B               P@8        @BX.::i:i:     B@2,:::i:i.  .
       Z@M     ;  ;@B     i@@@    ,ULYLJLL77@@i    uB@ivLYLJLJu:       ,B@B@B@B@B@B@B@B@B@B@        BOEOB@B@B@B@q  BZNO@B@B@B@B@@
  ,:i7JB@B@B@B@@u  B@:  :B@Bv               @Bi    J@B                  2J      uB@      :u:         @@r      @BL  7@X:       8BZ
B@B@B@B@B@,i.      kBBi@B@L                 B@i    j@@               uYjvJ2kSk1jM@@u2kFS1uLuJUi      iu@B@O   B@i  .iNB@Bj    B@u
 .     Z@M         :@B@Mi     :  rEXqXXXPS5U@Bi    Y@Bj1XXqkXXN07    B@Bq088OOGk@B@SE8OZZNq5@B@          i7:, @@,       ::i2r @B7
       MB@      ,8B@B@B      kB@ Y@@B@B@BBOGB@i    uB@EMB@B@B@B@j    @Bi        7@B         G@8    ukBB@@@B@P B@  .75BB@@@B@: B@:
       O@B  7u@B@BO, v@@v    B@G            @Bi    J@B               B@Y        uB@    7:,.i@BS   ,B@B1:     .@B  N@@BL       @B.
  5ri:r@B@  k@BL.     ,@B@q:5@B             B@r    1@@               @B7        F@B    @B@B@Or        .i.,,:1@B8       r,:::u@B@
  @B@B@B1               .q@B@B:             @Br    L@B                          5B@                   kB@B@@@5.       r@@@@B@Z;
           ,ijN   B@L   .             B@5                          .:...,:,:,.     ,,:.......                  ... .
 :@B@B@@@B@B@@@i  @B1  j@B@.         .@B      .B@B@B@@@B@B@B@B@B   G@B@B@B@B@B@B  .B@B@B@@@B@B@v    7;L7ri. @@@B@B@@ B@B@B@@@B@B@@
  NLrr:0B@        B@2    YB@@N       UBB       ... .      .@B@Bi              B@             @Br    B@BBB@8 B@   JBE         :B@
       :@B        BBk      .O:   E@B@B@B@B@B@P          .M@BS        ..,:,:,.7@@    ,.:,:::.,B@i    @B  :BS BB   B@           @B
:L77rr:E@@ir7vvvr:B@B:rv7ri:::rJ :7ij@Biir:@BM        :@B@i         v@B@@@B@B@@@   UB@B@B@B@B@BL    B@  i@5 M@  S@v  UB@B@@M  B@
8B@B@B@B@B@B@B@B@B@@@B@B@@@B@B@@L   JBM    @@i        5B@           @B.            @@               @B  ;@F BB  @B   O@L .@B  @B
       7B@        i@B               @@,    @B         L@B          ,B@..,:,,..    :@B..,,:,:.  .    B@  i@5 M@ .B@   NB.  B@  @@
       ;@B     ,,  B@      @@B.    U@B    0BE @B@B@B@B@B@B@B@B@B@  LBEOB@@@B@B@B  UO0G@B@B@B@B@Bi   @B  rBS MB. :@@  X@,  @B  @B
    ,;7B@@B@B@B@B  @B5   MB@q      @B7    B@          Y@B           :@5.      B@   OOv        @@    B@  i@5 M@.  jB5 kB.  B@  B@
7B@B@B@B@@1r:      ;@B.Z@@O        iB@@r B@j          vB@           ,1@B@B;  :@B   i0B@B@     @B    @B  ,BF MB.   @B 2@5i7@B  @B
 ::    7B@          B@B@u             7@B@B           Y@@                j , r@@        i :0 ,B@    B@LLG@F M@    @@ 0@@B@MZ  B@
       L@B       v@B@@@:     :@B:      B@B@B1.        jB@         :LLkBB@B@B 7@B  :7L0@B@@@B :@@    @@MO@BO BB2B@B@7 Y@       @@
       7B@  .7B@B@B7 :B@u    qB@    .@B@  .@B@:       7@B         O@@B7,     BBO  B@BMi      SB@    B@   :  B@.:i:            B@
  u::.,B@B  LB@Gi     .B@B2.:B@i  uB@B7         rL::,:@B@             :.   ,P@@:      :,  .:uB@r            @B.         .:.  U@@
  B@B@BBS                5B@BM:   MB            v@@@@@Mv              @@B@B@Bv        B@@@B@Bu              M@          .@B@B@X
*/
/*
                             UM.
                            J@B@1                                                                    iO@1
                           Y@@@B@BB.                                                              7B@B@B@
                          :@B@i,B@B@O                                                          ,Z@B@B@B@Br
                          @B@q   i@B@BS                                                      7@B@@@O5vMB@q
                         8@@B      LB@B@i                                                  FB@@@BNjYjLE@B@
                        ,B@B:        0@@@Z                                               P@B@BM1JJ125JPB@B
                        B@BB          :@B@B                                            XB@B@Z2LuU52F2u2@B@.
                       :@B@             @@@B:                                        v@B@B8uJj51F1525uUB@B7
                       @B@O              0@@B.               ..::ir7vvYUuU777r::.   B@B@OULU2F2F151F11Y@B@S
                       B@B,               8B@B  :ruXMB@B@B@B@B@B@B@B@B@B@@@B@B@B@B@B@B@5Jj1211F1F1F2FUJO@BB
                      U@B@                 @B@B@B@B@B@@@B@B@B@MMqPS5JuYL7rq@B@OBB@B@B8Yu211F1515251515YGB@@
                      @B@u                 v@@@@MSur:.                    LB@MvvjJuU5YU252F1F1F25251F2uX@@@
                      @@@.                                                N@BML2U2UUU12F15252525251515Jk@@B
                     r@B@                                                 YB@Bju52121252515252F15251F2u5@B@
                     PB@B                                                  @@@PYUF151F25151F152F2F1F15jF@@B
                     @@BS                                                  N@@@UJ2F25252F251525151F1F1u5@B@
                     @@@7                                                   B@B@5Yj12F152F1F1F25252515jFB@B
                     B@Bi                                                    M@B@O2Luu52525212F151121UY1@B@7
                    O@B@:                                                     v@B@BMSuYJJuuUu2u2uujjYJJXB@B@M
                  7B@B@,                                                        1B@@@B@GPF1uujuu21PNMB@B@B@B@@
                 qB@B2                                                            i8B@B@B@B@B@@@@@B@B@B@q: @@@B
                MB@B:                                                                 7SBB@B@B@B@B@Zu:      @B@B
               ZB@B.                                              ,v.                                        @B@L
              LB@B,                         Y7                    @B@Bu                                      7@B@
   :B@B@@B2:  @@B7                         @B@Z                   r@B@B@BP:                                   B@BE
    BB@@@B@B@B@BE                        r@B@B                       7@B@B@B@Ou:                              iB@B
         :uM@@B@@2.           :7::::ivk@B@B@0                           :5B@B@B@B@B@B@G.                       @B@i
            BB@@@B@@         :@B@B@@@B@B@@1                                 .i5M@B@B@@@5                       M@@2
            B@B ,@B1          L0EZZG0F7:                                            .:,                        uB@MrP@M7
           2@B@                                                                                               ,O@B@B@B@B
           @B@1                                                     :@B@@@r                                :@@@@B@BL:,,
           B@Bi                         :2ZS;                      :@B@B@B@r                               L@B@B@BU
           @B@.                        @@@B@B@                     vB@B@B@B5                                   @B@i
           B@B                        7B@B@B@BM                     OB@B@B@                                   ,B@B
           @B@                         @B@B@@@i                       rL7.                                    B@BM
           B@B7.:                       NB@@M.                                                               .@B@.
  .;JEB@@@B@B@B@B@.                                                                                       .  @B@u
@@@B@B@B@B@@@B@18U                                                                                      :B@B@B@BU,
7@BOui.    ,@@B                                                                                          SP@B@B@B@B@Or
            @@@U                                                                                           B@BJ.YO@B@B@i
            r@B@                                                                                         :B@Bk     .k@B@
             B@B@                                                                                       LB@@k         2i
              B@BM                                      .7jXEGqF7:                                     OB@@L
              .B@BM                                   .B@B@B@B@B@B@.                                 :@B@B:
               .B@B@                                   @@MYr::ivG@B                                .M@B@G
                 B@@@S                                                                           ,MB@B@,
                  v@@@BF                                                                      .1B@B@Br
                    2@@B@BL                                                                ,FB@@@B8,
                      r@B@B@BF,                                                        :YBB@B@B@B
                         L@B@B@B@P7,                                           .ivXB@B@B@B@B@M@B@
                            ,1B@B@B@B@@@BOP2L7i:,.              ..,:i7LSNB@@B@B@@@B@B@B@Z5v;.LB@@
                              @B@OEB@B@@@B@B@B@B@B@B@B@B@@@B@B@B@B@B@@@B@B@B@B@BM0SJ7i::::i:,u@B@
                              B@Bu ::i;7vu2XNGOMB@B@BMB@B@B@B@B@B@@@B1UFuj77ii:::::::iir;r;i.YB@B
                              @B@L.:i:i:i::::::::::..Y@B@BMYi:i;SB@B@N:.::i:iirir;r;rii::::ivO@B@
                              B@@X::,::::iirir;riri:E@B@1         ,@B@Br:;;r;rii:i::::i7JEB@@@@@B
                              @@@B@BBq5v7ii:::::::.2@@@i  ..,..     @B@@,,:::::irv2XMB@B@B@B@2@B@:
                             .B@BBB@@@B@B@B@BMNP5u7@B@1 .,,:,,  :.   @B@P50MB@B@B@B@B@@@BS:   @@B1
                             E@B@   ijGB@B@B@B@B@B@B@Bi .,:,,..@@B@7 B@B@B@B@B@B@BM57.        kB@B
                            .@B@:          .,ivu5Nq@B@u  ..,.. SB@B@@@B@PL7i,                 ,@B@
                            @@@8                   i@B@:    .     :B@B@@                       B@@2
                          i@@@@                     0@B@u          B@@B.                       vB@B
                         ,@B@G                       L@B@BOv:.:iFB@B@M                          @B@Bi
                          vNi                          S@@B@B@B@B@BM:                            MB@N
                                                          758BMqJ,

                 .  YO.               vq                            :G       Z:
        SqOMBB@B@Br @@r rBE           @B     B@@@@@B@ONX8k    i::::.OB1.:::.u@O.::::i           @B@B@U:@@B@@BPEBu
        B@@NB@k.    5@i  uB@E.        BM     1U2uUJvirB@@Z   r@@B@B@@@B@B@B@B@B@@@B@Bi   LB@B@1 BX :@k uLLLvr@BJ:
            iB      iBi    7@     .@M8@BGMZZ         @@F            ,B       Pi          v@  Bq @i v@        B@
       vuL7r8@S7vJL7N@Z7LLri;72.   F7@Bvvv@@       @BX         @@@B@B@@@@@B@@@B@B@B      7@  @F Bi @q  @B@Bu @B
       N@B@G@@@8@BBOMB@G@BMNXG@,     B@   @@      .Bk          .:u;    i@:      Zv       7@  Bk @,;@  ,BY @B B@
            r@       @G     5.      ,@v   BZ :::,.r@E .::i,      @B     B@    .@BL       7@  @F B:i@. .@  @M @B
            7B: ,vO, @@   iB@:      @B   7@:MB@B@B@@@B@B@BM       @@.    B:  2@q         7@  BS @i 0@  B. @O B@
       ,r2EBB@B@B@Bi G@  @BB        B@   @B        @S              :    r@   ..          7B  @F @7  B7 @  @B @B
       E@B@UOBr       @B@Bi          L@0PB        .BZ        .@B@B@B@B@B@B@B@B@B@B@B@,   r@  BF @i  @G B@B@B B@
            7@,      kB@U    ;r        @@@.       .@Z                GBuL@iBBi           vB@B@q BP:5@7 @u,.  @B
            LBi   YB@BrB@    @@       @B:L@Br      BM             .M@B  rB  rB@J         v@. Pi @XZ8r  .     B@
        .   G@i B@BM.  ,B@,  @B    iB@B    N, 7r..q@k         ,LB@B8    J@,   i@B@B1r           Br           @@
        MB@B@B  ,i       B@B@B,    B@:        @B@B@F         .@BB:      P@i      :OBZ          .@U       B@B@B:
                          .ll                                           rB.                     :
*////////////////////
//******************/
//*   I<3   C++    */
//*  I WANT ANY AC */
//* I LOVE PROGRAM!*/
//*IT'S INTERESTING*/
//* I LOVE PROGRAM!*/
//*  IN CONTESTS   */
//*   GET SCORE    */
//*    AC CODE     */
//*     LET'S      */
//*      GO        */
//*  Written by:   */
//*    gbc		   */
//******************/
/////////////////////
#include <bits/stdc++.h>
using namespace std;
#define fro for
#define itn int
#define mp make_pair
#define pb push_back
#define one first
#define two second
#define fi(n) n.begin()
#define se(n) n.end()
#define all(n) (n).begin(),(n).end()
#define po(n) n.pop()
#define PI 3.141592653
#define son(n) int lf=2*n,ri=2*n+1
#define pr (int prime[]={0,2,3,5,7,11,13,17,19,23,29,31,37})
#define sz(n) n.size()
#define big int maxi=-1
#define rep(i,n) for(int (i)=1;(i)<=(n);(i)++)
#define small int mini=1e9+7
#define op(x) freopen(x,"r",stdin)
#define wr(x) freopen(x,"w",stdout)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pair<int,int> > pipi;
typedef vector<int> vi;
typedef map<int,int> mii;
typedef map<string,int> msi;
typedef stack<int> sti;
typedef set<int> jihe;
typedef queue<int> qi;
typedef vector<pair<int,int> > vp;
typedef priority_queue<int,vector<int>,greater<int> > pqi;
typedef priority_queue<pii,vector<pii>,greater<pii> > pqpi;
const int inf=1e9+7;
const int maxn=5005;
const int maxm=200005;
int Read(){
    int x=0,t=1;char c=getchar();
    if(c=='-') {t=-1;c=getchar();}
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return t*x;
}

/*-------------------------------main part------------------*/

int n,m,cnt;
int dp[100000+5];
int a[1000005];
bool ok[100000+5][100000+5];
pii edge[1000005];
vi va;
vector<int> v[1000005],r[1000005];
int in[1000005],cur[1000005]; 
bool vis[1000005];

/*---------------------------declare * function-------------*/

void dfs1(int x)
{
	if(vis[x]) return;
	vis[x]=1;
	for(int i=0;i<r[x].size();i++)
	{
		if(!vis[r[x][i]])
		{
			dfs1(r[x][i]);
		}
	}
	va.push_back(x);
}

void dfs2(int x,int y)
{
	if(vis[x]) return;
	vis[x]=1;
	in[x]=y;
	for(int i=0;i<v[x].size();i++)
	{
		if(!vis[v[x][i]])
		{
			dfs2(v[x][i],y);
		}
	}
}


void dfs3(int x)
{
	if(dp[x]) return;
	for(int i=1;i<=cnt;i++)
	{
		if(i!=x && ok[i][x])
		{
			dfs3(i);
			dp[x]=max(dp[x],dp[i]);
		}
	}
	dp[x]+=cur[x];
}

/*---------------------------function * main----------------*/
int main()
{
	ios_base::sync_with_stdio(false);
	cin>>n>>m;
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	{
		a[i]=1;
	}
	for(int i=1;i<=m;i++)
	{ 
		int x,y;
		cin>>x>>y;
		edge[i].first=x;
		edge[i].second=y;
		v[x].push_back(y);
		r[y].push_back(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i]) dfs1(i);
	}
	reverse(va.begin(),va.end());
	memset(vis,0,sizeof(vis));
	cnt=0;
	for(int i=0;i<va.size();i++)
	{
		if(!vis[va[i]])
		{
			cnt++;
			dfs2(va[i],cnt);
		}
	}
	memset(cur,0,sizeof(cur));
	for(int i=1;i<=n;i++)
	{
		cur[in[i]]+=a[i];
	}
	memset(ok,0,sizeof(ok));
	for(int i=1;i<=m;i++)
	{
		int x=edge[i].first,y=edge[i].second;
		ok[in[x]][in[y]]=1;
	}
	memset(dp,0,sizeof(dp));
	int ans=-1;
	for(int i=1;i<=cnt;i++)
	{
		if(!dp[i]) dfs3(i);
		ans=max(ans,dp[i]);
	}
	cout<<ans-1<<endl;
	return 0;
}

//BY GBBECN


Compiler output:
/tmp/ccMej3PS.o: in function `dfs1(int)':
a.cc:(.text+0x96): relocation truncated to fit: R_X86_64_PC32 against symbol `vis' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0xae): relocation truncated to fit: R_X86_64_PC32 against symbol `vis' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0xd5): relocation truncated to fit: R_X86_64_PC32 against symbol `r' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0xf3): relocation truncated to fit: R_X86_64_PC32 against symbol `vis' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0x118): relocation truncated to fit: R_X86_64_PC32 against symbol `r' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0x158): relocation truncated to fit: R_X86_64_PC32 against symbol `r' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0x17f): relocation truncated to fit: R_X86_64_PC32 against symbol `va' defined in .bss section in /tmp/ccMej3PS.o
/tmp/ccMej3PS.o: in function `dfs2(int, int)':
a.cc:(.text+0x1ab): relocation truncated to fit: R_X86_64_PC32 against symbol `vis' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0x1c3): relocation truncated to fit: R_X86_64_PC32 against symbol `vis' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0x1db): relocation truncated to fit: R_X86_64_PC32 against symbol `in' defined in .bss section in /tmp/ccMej3PS.o
a.cc:(.text+0x207): additional relocation overflows omitted from the output
collect2: error: ld returned 1 exit status