UVAoj 11324 - The Largest Clique(tarjan + dp)

题意：给定一个有向图，寻找一个点数最大集合，使得这个集合中的任意两个点
u,v, 都有u- v 或者 v- u 或者u == v

思路：首先将强连通分量通过tarjan算法求出来，然后进行缩点，也就是每一个缩点
所组成的图就是一个DAG图！令每一个点的权值就是这个缩点所包含节点（也就是对应的
强连通分量的节点数目），因为强连通分量的任意的两个节点都是相互可达的，那么这个

缩点要么选要么不选，问题就转换成了DAG图上的最长路径！

#include iostream 

#include queue 

#include stack 

#include cstring 

#include cstdio 

#include algorithm 

#include vector 

#define N 1005

using namespace std;

struct EDGE{

 int u, v, nt;

 EDGE(){}

 EDGE(int u, int v, int nt) : u(u), v(v), nt(nt){}

int first[N];

vector EDGE 

vector EDGE 

int scc_cnt, dfs_clock;

int scc[N];

int pre[N], low[N];

int dp[N], cnt[N];

int in[N];

int n, m;

stack int 

void dfs(int u){

 pre[u] = low[u] = ++dfs_clock;

 s.push(u);

 for(int i = first[u]; ~i; i = g[i].nt){

 int v = g[i].v;

 if(!pre[v]){

 dfs(v);

 low[u] = min(low[u], low[v]);

 }else if(!scc[v])

 low[u] = min(low[u], pre[v]);

 if(low[u] == pre[u]){

 ++scc_cnt;

 while(1){

 ++cnt[scc_cnt];

 int x = s.top(); s.pop();

 scc[x] = scc_cnt;

 if(x==u) break;

void addEdge(int u, int v){

 g.push_back(EDGE(u, v, first[u]));

 first[u] = g.size() - 1;

void tarjans(){

 memset(pre, 0, sizeof(pre));

 memset(scc, 0, sizeof(scc));

 memset(cnt, 0, sizeof(cnt));

 memset(dp, 0, sizeof(dp));

 memset(in, 0, sizeof(in));

 scc_cnt = 0;

 dfs_clock = 0;

 for(int i=1; i ++i)

 if(!pre[i]) dfs(i);

 int len = g.size();

 memset(first, -1, sizeof(first));

 gg.clear();

 for(int i=0; i ++i)

 if(scc[g[i].u] != scc[g[i].v]){

 in[scc[g[i].v]]++;

 gg.push_back(EDGE(scc[g[i].u], scc[g[i].v], first[scc[g[i].u]]));

 first[scc[g[i].u]] = gg.size() - 1;

 int maxN = 0; 

 queue int 

 for(int i=1; i =scc_cnt; ++i)

 if(!in[i]){

 dp[i] = cnt[i];

 q.push(i);

 if(maxN dp[i]) maxN = dp[i];

 while(!q.empty()){

 int u = q.front(); q.pop();

 for(int i=first[u]; ~i; i = gg[i].nt){

 int v = gg[i].v;

 dp[v] = max(dp[v], dp[u] + cnt[v]);

 q.push(v);

 if(maxN dp[v]) maxN = dp[v];

 printf("%d\n", maxN); 

int main(){

 int t;

 scanf("%d", 

 while(t--){

 memset(first, -1, sizeof(first));

 scanf("%d%d", n, 

 while(m--){

 int u, v;

 scanf("%d%d", u, 

 addEdge(u, v);

 tarjans(); 

 g.clear();

 return 0;

}

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or
Find the contiguous subarray within an array (containing at least one number) which has the largest sum. For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9