暑假集训day2补充

暑假集训day2补充"/>

暑假集训day2补充

那天题没做完，今天补上了。

这是强连通分量的题

最大团——UVA11324

#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
#include<stack>
using namespace std;
const int maxn=1010;
inline int read(){int num=0,t=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')t=-1;c=getchar();}while(c<='9'&&c>='0'){num=(num<<3)+(num<<1)+c-'0';c=getchar();}return num*t;
}
vector<int>g[maxn];stack<int>S;
int pre[maxn],low[maxn],biao[maxn],t,cnt;
void dfs(int x){pre[x]=low[x]=++t;S.push(x);for(int i=0;i<g[x].size();i++){int y=g[x][i];if(!pre[y]){dfs(y);low[x]=min(low[x],low[y]);}else if(!biao[y])low[x]=min(low[x],pre[y]);}if(low[x]==pre[x]){cnt++;while(1){int s=S.top();S.pop();biao[s]=cnt;if(s==x)break;}}
}
void find_scc(int n){t=cnt=0;memset(pre,0,sizeof(pre));memset(biao,0,sizeof(biao));for(int i=0;i<n;i++)if(!pre[i])dfs(i);
}
int size[maxn],tg[maxn][maxn],d[maxn];
int dp(int x){if(d[x]>=0)return d[x];d[x]=size[x];for(int y=1;y<=cnt;y++)if(y!=x&&tg[x][y])d[x]=max(d[x],dp(y)+size[x]);return d[x];
}
int main(){int T=read(),n,m;while(T--){n=read();m=read();for(int i=0;i<n;i++)g[i].clear();for(int i=0;i<m;i++){int x=read(),y=read();g[x-1].push_back(y-1);}find_scc(n);memset(tg,0,sizeof(tg));memset(size,0,sizeof(size));for(int i=0;i<n;i++){size[biao[i]]++;for(int j=0;j<g[i].size();j++)tg[biao[i]][biao[g[i][j]]]=1;}int ans=0;memset(d,-1,sizeof(d));for(int i=1;i<=cnt;i++)ans=max(ans,dp(i));printf("%d\n",ans);}return 0;
}

本文由Yzyet编写，网址为wwwblogs/Yzyet。非Yzyet同意，禁止转载，侵权者必究。

转载于:.html