#include <bits/stdc++.h>
using i64 = int64_t;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, m;
std::cin >> n >> m;
std::vector<int> val(n);
for (auto &it : val) std::cin >> it;
std::vector<std::vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
g[u].push_back(v);
}
std::vector<int> dfn(n, -1), low(n), col(n, -1);
int DFN = 0, color = 0;
std::vector<int> stk;
std::function<void(int)> dfs = [&](int u) {
dfn[u] = low[u] = DFN++;
stk.push_back(u);
for (auto v : g[u]) {
if (dfn[v] == -1) {
dfs(v);
low[u] = std::min(low[u], low[v]);
} else if (col[v] == -1) {
low[u] = std::min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
int temp;
do {
temp = stk.back();
stk.pop_back();
col[temp] = color;
} while (temp != u);
col[temp] = color;
color++;
}
};
for (int i = 0; i < n; i++) {
if (dfn[i] == -1) {
dfs(i);
}
}
std::vector<int> new_val(color);
std::vector<std::vector<int>> h(color);
std::vector<int> d(color);
for (int i = 0; i < n; i++) {
new_val[col[i]] += val[i];
for (auto v : g[i]) {
if (col[i] != col[v]) {
h[col[i]].push_back(col[v]);
d[col[v]] += 1;
}
}
}
std::vector<int> dp(color), Q;
for (int i = 0; i < color; i++) {
if (d[i] == 0) {
Q.push_back(i);
dp[i] = new_val[i];
}
}
for (int i = 0; i < (int)Q.size(); i++) {
int u = Q[i];
for (auto v : h[u]) {
dp[v] = std::max(dp[v], dp[u] + new_val[v]);
if (--d[v] == 0) {
Q.push_back(v);
}
}
}
int ans = *std::max_element(dp.begin(), dp.end());
std::cout << ans << '\n';
return 0;
}
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const int MAXN=50005;
const ll mod=1e9+7;
void _io(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
struct EDGE{
int to,nxt;
}edge[300005<<1];
int n,m,head[MAXN],dfn[MAXN],low[MAXN],clr[MAXN],eban[300005<<1],cnt=1,timer;
void add(int u,int v){
edge[++cnt]={v,head[u]};
head[u]=cnt;
}
void tarjan(int u,int e){
dfn[u]=low[u]=++timer;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(!dfn[v]){
tarjan(v,i);
if(dfn[u]<low[v]) eban[i]=eban[i^1]=1;
low[u]=min(low[u],low[v]);
}
else if(i!=(e^1)) low[u]=min(low[u],dfn[v]);
}
}
void dfs(int u,int C){
clr[u]=C;
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].to;
if(clr[v]||eban[i]) continue;
dfs(v,C);
}
}
int main(){
_io();
cin>>n>>m;
for(int u,v,i=1;i<=m;i++){
cin>>u>>v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,0);
int clrcnt=0;
for(int i=1;i<=n;i++) if(!clr[i]) dfs(i,++clrcnt);
cout<<clrcnt;
return 0;
}
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=20050,MAXE=100050;
int n,m,iu,iv,head[MAXN],cnt=1,ans=0,rt;
int dfn[MAXN],low[MAXN],dfncnt,cut[MAXN];
struct EDGE{
int to,nxt;
}edge[MAXE*2];
void add_edge(int iu,int iv){
edge[++cnt]=((EDGE){iv,head[iu]});
head[iu]=cnt;
}
void tarjan(int now){
dfn[now]=low[now]=++dfncnt;
int soncnt=0;
for(int i=head[now];~i;i=edge[i].nxt){
int to=edge[i].to;
if(!dfn[to]){
soncnt++;
tarjan(to);
low[now]=min(low[now],low[to]);
if((soncnt>=2&&now==rt)||(now!=rt&&low[to]>=dfn[now])){
cut[now]=1;
}
}
else{
low[now]=min(low[now],dfn[to]);
}
}
}
int main(){
memset(head,-1,sizeof head);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&iu,&iv);
add_edge(iu,iv);
add_edge(iv,iu);
}
for(int i=1;i<=n;i++){
if(!dfn[i]){
rt=i;
tarjan(i);
}
}
for(int i=1;i<=n;i++){
if(cut[i]){
ans++;
}
}
printf("%d\n",ans);
for(int i=1;i<=n;i++){
if(cut[i]){
printf("%d ",i);
}
}
return 0;
}
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
const int MAXN=1000005;
const ll mod=1e9+7;
void _io(){std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
int n,m,head[MAXN<<1],dfn[MAXN<<1],low[MAXN<<1],clr[MAXN<<1],timer=1,CLR;
vector<int> g[MAXN<<1];
stack<int> S;
void dfs(int u){
dfn[u]=low[u]=++timer;
S.push(u);
for(auto v:g[u]){
if(!dfn[v]){
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(!clr[v]){
low[u]=min(low[u],dfn[v]);
}
}
if(dfn[u]==low[u]){
++CLR;
int x;
do{
x=S.top();S.pop();
clr[x]=CLR;
}while(x!=u);
}
}
int main(){
_io();
cin>>n>>m;
for(int u,a,v,b,i=1;i<+m;i++){
cin>>u>>a>>v>>b;
g[u+(a)*1000000].push_back(v+(b^1)*1000000);
g[v+(b)*1000000].push_back(u+(a^1)*1000000);
}
for(int i=1;i<=2000000;i++){
if(!dfn[i]) dfs(i);
}
bool ANS=true;
for(int i=1;i<=n;i++){
if(clr[i]==clr[i+1000000]) ANS=false;
}
if(!ANS){
cout<<"IMPOSSIBLE";
}
else{
cout<<"POSSIBLE\n";
for(int i=1;i<=n;i++)
cout<<(clr[i]<clr[i+1000000]?1:0)<<' ';
}
return 0;
}
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=100050,MAXE=300050;
int n,m,ia,ib;
int head[MAXN],dfn[MAXN],low[MAXN],ins[MAXN],stk[MAXN],vis[MAXN],evis[MAXN],clr[MAXN],ind[MAXN],outd[MAXN];
int stkcnt,dfncnt,clrcnt,cnt=1;
struct EDGE{
int to,nxt;
}edge[MAXE];
void add_edge(int iu,int iv){
edge[++cnt]=((EDGE){iv,head[iu]});
head[iu]=cnt;
}
void tarjan(int u){
dfn[u]=low[u]=++dfncnt;
ins[u]=vis[u]=1;
stk[++stkcnt]=u;
for(int i=head[u];~i;i=edge[i].nxt){
if(evis[i]) continue;
evis[i]=evis[i^1]=1;
int v=edge[i].to;
if(ins[v]) low[u]=min(low[u],dfn[v]);
else if(!vis[v]) tarjan(v),low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u]){
clrcnt++;
while(stk[stkcnt]!=u){
clr[stk[stkcnt]]=clrcnt;
ins[stk[stkcnt--]]=0;
}
clr[stk[stkcnt]]=clrcnt;
ins[stk[stkcnt--]]=0;
}
}
int main(){
int ans=0;
memset(head,-1,sizeof head);
cnt=1;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&ia,&ib);
add_edge(ia,ib);
add_edge(ib,ia);
}
for(int i=1;i<=n;i++){
if(!vis[i]){
stkcnt=0;
tarjan(i);
}
}
for(int i=1;i<=n;i++){
for(int j=head[i];~j;j=edge[j].nxt){
int v=edge[j].to;
if(clr[i]==clr[v]) continue;
outd[clr[i]]++,ind[clr[v]]++;
}
}
for(int i=1;i<=clrcnt;i++){
if(ind[i]==1||outd[i]==1){
ans++;
}
}
printf("%d",(ans+1)/2);
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <deque>
#include <bitset>
#include <cassert>
#include <unordered_set>
#include <unordered_map>
#define ll long long
using namespace std;
const int MAXN=300050;
ll inp1,inp2,inp3,s,t,ver[2];
ll n,m,head[MAXN],dep[MAXN],cnt=1;
ll dfn[MAXN],low[MAXN],clr[MAXN],ins[MAXN],stk[MAXN],evis[MAXN*2],dfncnt=0,clrcnt=0,stktop=0;
struct EDGE{
ll fr,to,nxt;
bool operator<(const EDGE& b)const{return clr[to]==clr[b.to]?clr[fr]<clr[b.fr]:clr[to]<clr[b.to];}
bool operator==(const EDGE& b)const{return clr[to]==clr[b.to]&&clr[fr]==clr[b.fr];}
}edge[MAXN*2];
void add_edge(ll u,ll v){
edge[++cnt].fr=u;
edge[cnt].to=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
void rebuild(){
ll CNT=cnt;
memset(head,0,sizeof head);cnt=1;
sort(edge+2,edge+CNT+1);
CNT=unique(edge+2,edge+CNT+1)-(edge+2);
for(ll i=2;i<=CNT+1;i++){
if(clr[edge[i].fr]!=clr[edge[i].to]){
add_edge(clr[edge[i].fr],clr[edge[i].to]);
// printf("%lld->%lld\n",clr[edge[cnt].fr],clr[edge[cnt].to]);
}
}
}
void tarjan(ll u){
dfn[u]=low[u]=++dfncnt;
stk[++stktop]=u;ins[u]=1;
for(ll i=head[u];i;i=edge[i].nxt){
if(evis[i]||evis[i^1]) continue;
evis[i]=1;
ll v=edge[i].to;
if(ins[v]) low[u]=min(low[u],dfn[v]);
else if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
}
if(dfn[u]==low[u]){
++clrcnt;
while(stk[stktop]!=u){
clr[stk[stktop]]=clrcnt;
ins[stk[stktop--]]=0;
}
clr[stk[stktop]]=clrcnt;
ins[stk[stktop--]]=0;
}
}
void dfs(ll u,ll fa,ll id){
dep[u]=dep[fa]+1;
if(dep[u]>dep[ver[id]]) ver[id]=u;
for(ll i=head[u];i;i=edge[i].nxt){
ll v=edge[i].to;
if(v==fa) continue;
dfs(v,u,id);
}
}
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=m;i++){
scanf("%lld%lld",&inp1,&inp2);
add_edge(inp1,inp2);
add_edge(inp2,inp1);
}
for(ll i=1;i<=n;i++){
if(!dfn[i]) tarjan(i);
}
rebuild();
dfs(1,0,0);
dfs(ver[0],0,1);
printf("%lld",dep[ver[1]]-1);
// system("pause");
return 0;
}
#include <bits/stdc++.h>
#define inf(i,l,r) for(int i=l;i<=r;i++)
#define def(i,l,r) for(int i=l;i>=r;i--)
#define ll long long
using namespace std;
int N,M,tmpu,tmpv,top,ans=0;
struct EDGE{
int to,next;
}Aedge[50005],Bedge[50005];
int Ahead[10005],Acnt=0,Bhead[10005],Bcnt=0;
int dfn[10005]={0},low[10005]={0},vis[10005]={0},tarcnt=0,out[10005]={0};
int value[10005]={0},cow[10005],clr[10005]={0},clrcnt=0;
stack<int> Stk;
queue<int> Q;
void Aadd(int u,int v){
Aedge[Acnt].to=v;
Aedge[Acnt].next=Ahead[u];
Ahead[u]=Acnt++;
}
void Badd(int u,int v){
Bedge[Bcnt].to=v;
Bedge[Bcnt].next=Bhead[u];
Bhead[u]=Bcnt++;
}
void Tarjan(int node){
dfn[node]=low[node]=++tarcnt;
vis[node]=1;
Stk.push(node);
for(int i=Ahead[node];i!=-1;i=Aedge[i].next){
int to=Aedge[i].to;
if(!dfn[to]){
Tarjan(to);
low[node]=min(low[node],low[to]);
}
else if(vis[to]){
low[node]=min(low[node],low[to]);
}
}
if(dfn[node]==low[node]){
clr[node]=++clrcnt;
value[clrcnt]++;
top=Stk.top();
Stk.pop();
while(top!=node){
vis[top]=0;
clr[top]=clrcnt;
value[clrcnt]++;
top=Stk.top();
Stk.pop();
}
vis[node]=0;
}
}
int main(){
scanf("%d%d",&N,&M);
inf(i,0,N){
Ahead[i]=Bhead[i]=-1;
}
inf(i,1,M){
scanf("%d%d",&tmpu,&tmpv);
Aadd(tmpu,tmpv);
}
inf(i,1,N){
if(!dfn[i]){
Tarjan(i);
}
}
inf(i,1,N){
for(int j=Ahead[i];j!=-1;j=Aedge[j].next){
int v=Aedge[j].to;
if(clr[i]==clr[v]) continue;
Badd(clr[i],clr[v]);
out[clr[i]]++;
}
}
// cout<<endl;
// inf(i,1,N){
// cout<<i<<" clr: "<<clr[i]<<" size: "<<value[clr[i]]<<endl;
// }
// cout<<endl;
inf(i,1,clrcnt){
cow[i]=value[i];
if(!out[i]){
if(ans){
printf("0");
return 0;
}
ans=cow[i];
}
}
// while(!Q.empty()){
// int u=Q.front();
// Q.pop();
// if(value[u]==N){
// ans+=cow[u];
// }
// for(int i=Bhead[u];i!=-1;i=Bedge[i].next){
// int v=Bedge[i].to;
// in[v]--;
// value[v]=max(value[v],value[u]+cow[v]);
// if(!in[v]){
// Q.push(v);
// }
// }
// }
printf("%d",ans);
// cout<<endl;
// inf(i,1,N){
// cout<<i<<" clr: "<<clr[i]<<" size: "<<value[clr[i]]<<endl;
// }
// cout<<endl;
return 0;
}
/*******************************************
Note:
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*******************************************/
#include <queue>
#include <math.h>
#include <stack>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <iomanip>
#include <string.h>
#include <algorithm>
using namespace std;
#define ll long long
const int N=2e5+10;
const int INF=0x3f3f3f3f;
int n,d,T,x[N],y[N];
char a[N],c1[N],c2[N];
int ff[N];
int head[N],to[N],ne[N],id;
int st[N],top,num,vis[N];
int flag=1,dfn[N],low[N],col[N],cnt;
void init()
{
id=num=top=cnt=0;
memset(head,0,sizeof head);
memset(to,0,sizeof to);
memset(ne,0,sizeof ne);
memset(dfn,0,sizeof dfn);
memset(vis,0,sizeof vis);
memset(st,0,sizeof st);
memset(col,0,sizeof col);
memset(low,0,sizeof low);
}
void add(int x,int y)
{
id++;
to[id]=y,ne[id]=head[x],head[x]=id;
}
void tarjan(int u){
dfn[u]=low[u]=++num;
st[++top]=u;
vis[u]=1;
for(int i=head[u];i;i=ne[i]){
int v=to[i];
if(!dfn[v]){
tarjan(v);
low[u]=min(low[v],low[u]);
}else if(vis[v])
low[u]=min(dfn[v],low[u]);
}
if(low[u]==dfn[u]){
cnt++;
while(1){
int v=st[top--];
col[v]=cnt;
vis[v]=0;
if(v==u)break;
}
}
}
int get(int idx,char ss)
{
if(a[idx]=='a')return ss=='B'?idx:idx + n;
if(a[idx]=='b'||a[idx]=='c')return ss=='A'?idx:idx+n;
}
int rev(int idx)
{
return idx <= n ? idx+n :idx-n;
}
void build()
{
init();
for(int i=1;i<=T;i++)
{
int t1=x[i],t2=y[i];
int is1=get(t1,c1[i]),is2=get(t2,c2[i]);
if(a[t1]-32==c1[i])continue;
if(a[t2]-32==c2[i])
{
add(is1,rev(is1));
continue;
}
add(is1,is2);
add(rev(is2),rev(is1));
}
}
void dfs(int step)
{
if(step>d)
{
build();
for(int i=1;i<=2*n;i++)
if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++)
{
if(col[i]==col[i+n])return;
}
flag=0;
return;
}
for(int i=0;i<=1;i++)
{
a[ff[step]]=i+'a';
dfs(step+1);
if(!flag)return;
}
}
int main()
{
cin>>n>>d;
scanf("%s",a+1);
cin>>T;
for(int i=1;i<=T;i++)
scanf("%d %c %d %c",&x[i],&c1[i],&y[i],&c2[i]);
int ss=1;
for(int i=1;i<=n;i++)
{
if(a[i]=='x')ff[ss++]=i;
}
dfs(1);
if(flag)cout<<-1;
else
{
for(int i=1;i<=n;i++)
{
if(a[i]=='a')
printf("%c",col[i]<col[i+n] ? 'B' : 'C');
if(a[i]=='b')
printf("%c",col[i]<col[i+n] ? 'A' : 'C');
if(a[i]=='c')
printf("%c",col[i]<col[i+n] ? 'A' : 'B');
}
}
return 0;
}
C20250038
LV 6
@
2023-8-10 10:42:41