Forest Program (DFS Method — Ring on Tree)

October 16, 2021By Simo Mathematics

The meaning of the title:

Every connected block in the desert is a cactus; a connected block is a cactus if and only if there are no heavy edges and self-rings in the connected block , And each side is only covered by at most one simple ring.

After some evaluation, country Z decided to finally turn the desert into a forest by deleting some edges in the desert. Here we define the forest to satisfy: every connected block in the forest is a tree, and the tree is a connected block with the number of edges equal to the number of points minus one. Now given one contains

 1 #define  IOS ios_base::sync_with_stdio(0); cin.tie(0);

 2 #include //sprintf islower isupper

 3 #include //malloc exit strcat itoa system("cls")

 4 #include //pair

 5 #include //freopen("C:\Users\13606\Desktop\draft.txt","r",stdin);

 6 #include 

 7 //#include 

 8 //#include

 9 #include 

 10 #include 

 11 #include <set>

 12 #include <string.h>//strstr substr

 13 #include <string>

 14 #include //srand(((unsigned)time(NULL))); Seed n=rand()%10-0~9;

 15 #include 

 16 #include 

 17 #include //priority_queue, greater> q;//less

 18 #include //emplace_back

 19 //#include 

 20 //#include //reverse(a, a+len);// ~! ~! floor

 21 #include //sort + unique: sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 22 using  namespace std;//next_permutation(a+1,a+1+n); //prev_permutation

 23 //******************

 24 int abss(int a);

 25 int lowbit(int n);

 26 int Del_bit_1(int n);

 27 int maxx(int a,int b);

 28 int minn(int a,int b);

 29 double fabss(double a);

 30 void swapp(int &a,int &b);

 31 clock_t __STRAT,__END;

 32 double __TOTALTIME;

 33 void _MS(){__STRAT=clock();}

 34 void _ME(){__END=clock( );__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}

 35 //***********************

 36 #define rint register int

 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)

 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)

 39 #define mem(a,b) memset(a,b ,sizeof(a))

 40 #define pr printf

 41 #define sc scanf

 42 #define ls rt<<1

 43 #define rs rt<<1|1

 44 typedef long long ll;

 45 const double E=2.718281828;

 46 const double PI=acos(-1.0);

 47 //const ll INF=(1LL<<60);

 48 const  int inf=(1<<30);

 49 const double ESP=1e-9;

 50 const int mod=(int)998244353;

 51 const int N=(int)5e5+10;

 52 int read(){

 53 int x=0,f=1;char ch =getchar();

 54 for(;!isdigit(ch); ch=getchar())if(ch=='-')f=-1< span style="color: #000000;">;

 55 for(;isdigit(ch);ch =getchar())x=x*10+ch-'0';

 56 return x*f;

 57 }

 58 ll qpow(ll a,ll b,ll mod)

 59 {

 60  ll ans;

 61 // a%=mod;

 62 ans=1;

 63 while(b!=0)

 64  {

 65 if(b&1)

 66 ans=(ans*a)%mod;

 67 b/=2;

 68 a=(a*a)%mod;

 69 }

 70 return ans;

 71 }

 72

 73 bool vis[N];

 74 ll dep[N];

 75 vectorint> >G(N);

 76

 77 ll loop,other,ans;

 78 void dfs(int u,int v)

 79 {

 80 // cout<

 81 if (vis[v])

 82  {

 83 if(dep[u]<=dep [v])return;

 84 ans*=qpow(2,dep[ u]+1-dep[v],mod)-1;

 85 ans=(ans+mod)%mod;

 86 loop+=dep[u]+1- dep[v];

 87 return;

 88 }

 89 vis[v]=1;

 90 dep[v]=dep[u]+1 span>;

 91 int sz=G[v].size();

 92 for(int i=0;ii)

 93  {

 94 int to=G[v][i];

 95 if(!dep[v]<= dep[to]&&to!=u)

 96  {

 97  dfs(v,to);

 98 }

 99 }

100 }

101

102 int main()

103 {

104 int n,way;

105 while(~sc("%d%d" ,&n,&way))

106  {

107 ans=1;loop=other=< span style="color: #800080;">0;

108 for(int i=1;i<=n;++i )

109 G[i].clear(),dep[i]=vis[i]=0;

110 for(int i=1;i<=way;++i )

111  {

112 int u,v;

113 u=read(),v=read();

114  G[u].push_back(v);

115  G[v].push_back(u);

116 }

117 // bfs({0,1});

118 dfs(0,1);

119 other=way-loop;

120 ans*=qpow(2,other,mod);

121 ans%=mod;

122 // if(loop==0)ans=0;

123 pr("%lld
",ans);

124 //cout<

125 }

126 return 0;

127 }

128

129 /************************************************** ************************************/

130

131 int maxx(int a,int b)

132 {

133 return a>b?a:b;

134 }

135

136 void swapp(int &a,int &b)

137 {

138 a^=b^=a^=b;

139 }

140

141 int lowbit(int n)

142 {

143 return n&(-n);

144 }

145

146 int Del_bit_1(int n)

147 {

148 return n&(n-1);

149 }

150

151 int abss(int a)

152 {

153 return a>0?a:-a;

154 }

155

156 double fabss(double a)

157 {

158 return a>0?a:-a;

159 }

160

161 int minn(int a,int b)

162 {

163 return aa:b;

164 }

 1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);

 2 #include //sprintf islower isupper

 3 #include //malloc exit strcat itoa system("cls")

 4 #include //pair

 5 #include //freopen("C:\Users\13606\Desktop\draft.txt","r",stdin);

 6 #include 

 7 //#include 

 8 //#include

 9 #include 

 10 #include 

 11 #include <set>

 12 #include <string.h>//strstr substr

 13 #include <string>

 14 #include //srand(((unsigned)time(NULL))); Seed n=rand()%10-0~9;

 15 #include 

 16 #include 

 17 #include //priority_queue, greater> q;//less

 18 #include //emplace_back

 19 //#include 

 20 //#include //reverse(a, a+len);// ~! ~! floor

 21 #include //sort + unique: sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 22 using  namespace std;//next_permutation(a+1,a+1+n); //prev_permutation

 23 //******************

 24 int abss(int a);

 25 int lowbit(int n);

 26 int Del_bit_1(int n);

 27 int maxx(int a,int b);

 28 int minn(int a,int b);

 29 double fabss(double a);

 30 void swapp(int &a,int &b);

 31 clock_t __STRAT,__END;

 32 double __TOTALTIME;

 33 void _MS(){__STRAT=clock();}

 34 void _ME(){__END=clock( );__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}

 35 //***********************

 36 #define rint register int

 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)

 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)

 39 #define mem(a,b) memset(a,b,sizeof(a))

 40 #define pr printf

 41 #define sc scanf

 42 #define ls rt<<1

 43 #define rs rt<<1|1

 44 typedef long long ll;

 45 const double E=2.718281828;

 46 const double PI=acos(-1.0);

 47 //const ll INF=(1LL<<60);

 48 const int inf=(1<<30);

 49 const double ESP=1e-9;

 50 const int mod=(int)998244353;

 51 const int N=(int)5e5+10;

 52 int read(){

 53     int x=0,f=1;char ch=getchar();

 54     for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1;

 55     for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;

 56     return x*f;

 57 }

 58 ll qpow(ll a,ll b,ll mod)

 59 {

 60     ll ans;

 61 //    a%=mod;

 62     ans=1;

 63     while(b!=0)

 64     {

 65         if(b&1)

 66             ans=(ans*a)%mod;

 67         b/=2;

 68         a=(a*a)%mod;

 69     }

 70     return ans;

 71 }

 72 

 73 bool vis[N];

 74 ll dep[N];

 75 vectorint> >G(N);

 76 

 77 ll loop,other,ans;

 78 void dfs(int u,int v)

 79 {

 80 //    cout<

 81     if(vis[v])

 82     {

 83         if(dep[u]<=dep[v])return;

 84         ans*=qpow(2,dep[u]+1-dep[v],mod)-1;

 85         ans=(ans+mod)%mod;

 86         loop+=dep[u]+1-dep[v];

 87         return;

 88     }

 89     vis[v]=1;

 90     dep[v]=dep[u]+1;

 91     int sz=G[v].size();

 92     for(int i=0;ii)

 93     {

 94         int to=G[v][i];

 95         if(!dep[v]<=dep[to]&&to!=u)

 96         {

 97             dfs(v,to);

 98         }

 99     }

100 }

101 

102 int main()

103 {

104     int n,way;

105     while(~sc("%d%d",&n,&way))

106     {

107         ans=1;loop=other=0;

108         for(int i=1;i<=n;++i)

109             G[i].clear(),dep[i]=vis[i]=0;

110         for(int i=1;i<=way;++i)

111         {

112             int u,v;

113             u=read(),v=read();

114             G[u].push_back(v);

115             G[v].push_back(u);

116         }

117         //    bfs({0,1});

118         dfs(0,1);

119         other=way-loop;

120         ans*=qpow(2,other,mod);

121         ans%=mod;

122         //    if(loop==0)ans=0;

123         pr("%lld
",ans);

124         //cout<

125     }

126     return 0;

127 }

128 

129 /**************************************************************************************/

130 

131 int maxx(int a,int b)

132 {

133     return a>b?a:b;

134 }

135 

136 void swapp(int &a,int &b)

137 {

138     a^=b^=a^=b;

139 }

140 

141 int lowbit(int n)

142 {

143     return n&(-n);

144 }

145 

146 int Del_bit_1(int n)

147 {

148     return n&(n-1);

149 }

150 

151 int abss(int a)

152 {

153     return a>0?a:-a;

154 }

155 

156 double fabss(double a)

157 {

158     return a>0?a:-a;

159 }

160 

161 int minn(int a,int b)

162 {

163     return aa:b;

164 }

DFS, forest, method, program, ring, Tree

Leave a Comment Cancel reply