#include<bits/stdc++.
h>
using namespace std;
#define int long long
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define fi first
#define se second
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
typedef vector<VI> VVI;
typedef map<int,int> MPII;
typedef set<int> SETI;
typedef multiset<int> MSETI;
VVI mat;
VVI vis;
int t,r,c;
int dx[]={-1,0,1,0}
int dy[]={0,1,0,-1}
bool IsSafe(int x,int y){
if(x>=1&&y>=1 && x<=r && y<=c && mat[x][y]==1)
return true;
return false;
}
void DFS(int x,int y){
mat[x][y]=-1;
for(int i=0;i<4;i++){
int newx=x+dx[i];
int newy=y+dx[i];
}
if(IsSafe(newx,newy)){
mat[x][y]=2;
DFS(newx,newy);
}
}
int32_t main()
{
cin>>t;
while(t--){
cin>>r>>c;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
cin>>mat[i][j];
}
}
int rotten=0;
for(int i=0;i<r;i++){
for(int j=0;j<c;j++){
if(mat[i][j==2]){
rotten++;
DFS(i,j);
}
}
}
cout<<"TIME"<<rotten<<endl;
}
return 0;
}
BFS
#include<bits/stdc++.h>
using namespace std;
int n,e;
unordered_map<char,vector<char>>adj;
void BFS(char src, char des){
unordered_map<char,int>dis;
unordered_map<char,char>par;
for(auto x:adj){
char cityname= [Link];
dis[cityname]=INT_MAX;
}
queue<char>q;
[Link](src);
dis[src]=0;
while(![Link]()){
auto u=[Link]();
cout<<u<<" ";
[Link]();
for(auto x:adj[u]){
if(dis[x]==INT_MAX){
[Link](x);
dis[x]=dis[u]+1;
par[x]=u;
}
}
}
cout<<"short dis from "<<src<<"To"<<des<<"is"<<dis[des];
while(des!=src){
cout<<des<<"<---";
des=par[des];
}
cout<<src<<endl;
}
int main(){
cin>>n>>e;
for(int i=0; i<e; i++){
char ch1,ch2;
cin>>ch1>>ch2;
adj[ch1].push_back(ch2);
adj[ch2].push_back(ch1);
}
char source='b',des='a';
BFS(source,des);
return 0;
}
bipartite
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int>adj[N];
int n,e;
vector<int>vis(N,-1);
void BFS(){
queue<pair<int,int>>q;
[Link]({1,1});
vis[1]=1;
while(![Link]()){
auto u=[Link]();
[Link]();
int currV=[Link];
int currC=[Link];
for(auto x:adj[currV]){
if(vis[x]==-1){
vis[x]=3-currC;
[Link]({x,vis[x]});
}
else if(vis[x]=currC){
cout<<"Vetex"<<currV<<"and"<<x<<"hv same c"<<currC<<endl;
return;
}
}
}
cout<<"graph bipartite";
}
void bipartite(){
int src=1;
BFS();
}
int main(){
cin>>n>>e;
for(int i=0; i<e; i++){
int ch1,ch2;
cin>>ch1>>ch2;
adj[ch1].push_back(ch2);
adj[ch2].push_back(ch1);
}
bipartite();
return 0;
}
DFS bipartite
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
vector<int>adj[N];
int n,e;
vector<int>vis(N,0);
map<int,int>mp;
map<int,int>par;
bool DFS(int src){
vis[src]=1;
for(auto x:adj[src]){
if(!vis[x])
{
cout<<src<<" "<<x<<endl;
mp[x]=3 -mp[src];
DFS(x);
}
else if(vis[x] && mp[x]==mp[src]){
cout<<"vertex"<<x<<" "<<src<<"hav same color"<<endl;
return false;
}
}
return true;
}
void bipartite(){
int src=1;
mp[src]=1;
par[src]=0;
DFS(src);
bool c;
if(c==false){
cout<<"graph noy bipartite";
}
else
cout<<"graph bipartite";
}
int main(){
cin>>n>>e;
for(int i=0; i<e; i++){
int ch1,ch2;
cin>>ch1>>ch2;
adj[ch1].push_back(ch2);
adj[ch2].push_back(ch1);
}
bipartite();
return 0;
}