# UVa 10278 – Fire Station

0

Solution Idea:

In this problem the most challenging part is determine how the input is given.
Here for each test case number of edge in the graph is not fixed. You need to take input till end of file. For this strignstream class is used.

And the algorithmic idea is similar like complete search. Place an additional fire station on every intersection which do not contain any fire station already. and run dijkstra for this graph. every time you place a new fire station on an intersection you have to run a dijkstra taking that node as source and also the existing fire stations by input as source. just print the minimum intersection number which minimize the maximum distance.

```
#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              1000000007
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define loop1(i,n)       for(int i=1;i<=n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

struct data
{
int u,cost;
data(int a,int b)
{
u=a,cost=b;
}
bool operator < (const data &p) const
{
return cost>p.cost;
}
};

vector<int>graph[600],cost[600];
ll dis[600];
bool vis[600];
set<int>st;
int f,k;

void all_clear(int n)
{
for(int i=0;i<=550;i++)
{
graph[i].clear();
cost[i].clear();
dis[i]=(1<<28);
vis[i]=0;
}
st.clear();
}

ll dijkastra(int src)
{
for(int i=0;i<600;i++) dis[i]=(1<<28);

priority_queue<data>Q;

stlloop(st)
{
dis[*it]=0;
Q.push(data(*it,0));
}
Q.push(data(src,0));
dis[src]=0;
ll ret=0;

while(!Q.empty())
{
data u=Q.top();
Q.pop();
for(int i=0;i<SZ(graph[u.u]);i++)
{
int v=graph[u.u][i];
if(u.cost+cost[u.u][i]<dis[v])
{
dis[v]=u.cost+cost[u.u][i];
Q.push(data(v,dis[v]));
}

}
}

for(int i=1;i<=k;i++)
ret=max(ret,dis[i]);
return ret;
}

int main()
{

//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
//    CIN;
int t;
cin>>t;
TEST_CASE(t)
{
//        vector<int>source;
cin>>f>>k;

all_clear(k);
st.clear();

for(int i=0;i<f;i++)
{
int a;
cin>>a;
dis[a]=0;
st.insert(a);
vis[a]=1;
}

string str;
getline(cin,str);

while(1)
{
getline(cin,str);
stringstream ss(str);
if(str.empty()) break;
int a,b,c;
ss>>a>>b>>c;
graph[a].pb(b);
graph[b].pb(a);
cost[a].pb(c);
cost[b].pb(c);
}

int ans=1,maxi=100000000;
for(int i=1;i<=k;i++)
{
if(vis[i]==0)
{
ll temp=dijkastra(i);
if(temp<maxi)
{
maxi=temp;
ans=i;
}
}
}

cout<<ans<<endl;
if(z!=t)
cout<<endl;
}

return 0;
}

```

# ACM-ICPC Live Archive : 4109 – USHER

0

```
/*
If opportunity doesn't knock, build a door.

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|S|.|S|.|R|.|A|.|S|.|A|.|M|.|K|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Success is how high you bounce when you hit bottom.
*/

#include <bits/stdc++.h>

#define pii              pair <int,int>
#define pll              pair <long long,long long>
#define sc               scanf
#define pf               printf
#define Pi               2*acos(0.0)
#define ms(a,b)          memset(a, b, sizeof(a))
#define pb(a)            push_back(a)
#define MP               make_pair
#define db               double
#define ll               long long
#define EPS              10E-10
#define ff               first
#define ss               second
#define sqr(x)           (x)*(x)
#define D(x)             cout<<#x " = "<<(x)<<endl
#define VI               vector <int>
#define DBG              pf("Hi\n")
#define MOD              10000019
#define CIN              ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)            (int)a.size()
#define sf(a)            scanf("%d",&a)
#define sfl(a)           scanf("%lld",&a)
#define sff(a,b)         scanf("%d %d",&a,&b)
#define sffl(a,b)        scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)      scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)     scanf("%lld %lld %lld",&a,&b,&c)
#define stlloop(v)       for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define loop(i,n)        for(int i=0;i<n;i++)
#define REP(i,a,b)       for(int i=a;i<b;i++)
#define RREP(i,a,b)      for(int i=a;i>=b;i--)
#define TEST_CASE(t)     for(int z=1;z<=t;z++)
#define PRINT_CASE       printf("Case %d: ",z)
#define CASE_PRINT       cout<<"Case "<<z<<": "
#define all(a)           a.begin(),a.end()
#define intlim           2147483648
#define infinity         (1<<28)
#define ull              unsigned long long
#define gcd(a, b)        __gcd(a, b)
#define lcm(a, b)        ((a)*((b)/gcd(a,b)))

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

vector<int>graph[505],cost[505];
int cap,p,usernum;

int aa=INT_MAX;

int bfs(int src, int dst)
{
int dis[505];
for(int i=0;i<505;i++) dis[i]=infinity;
dis[src]=0;
queue<int>Q;
Q.push(src);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
for(int i=0;i<SZ(graph[u]);i++)
{
int v=graph[u][i];
if(dis[u]+cost[u][i]<dis[v])
{
dis[v]=dis[u]+cost[u][i];
Q.push(v);
}
}
}
return dis[dst];
}

int main()
{

//     freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

int t;
while(sf(t)==1 && t)
{
TEST_CASE(t)
{
//            D(z);
for(int i=0;i<505;i++)
{
graph[i].clear();
cost[i].clear();
}
sff(cap,p);
vector<int>user;
sf(usernum);
loop(i,usernum)
{
int a;
sf(a);
user.pb(a);
}

for(int i=1;i<=p;i++)
{
int xx;
sf(xx);
for(int j=1;j<=xx;j++)
{
int a,b;
sff(a,b);
graph[i].pb(b);
cost[i].pb(a);
}
}

aa=INT_MAX;

for(int i=0;i<SZ(user);i++)
{
aa=min(aa,bfs(user[i],0));
}

if(aa==0)
{
pf("0\n");
continue;
}

{
int sum=0;
int ans=0;
sum=0;
while(sum<cap)
{
sum+=(aa);
if(sum>=cap) break;
sum--;
ans++;
}
pf("%d\n",ans);
}

}
}
return 0;
}

```

# UVa 762 – We Ship Cheap

0

## Solution Idea:

After reading the problem statement It’s clear that this is a shortest path problem and we can solve this using BFS. In this problem all the nodes are string. so we use map for mapping strings with integers and run a BFS.

The main problem is is problem is it’s test cases. This problem have a lots of critical case. Like source and destination is not present on the input graph and Source and Destination is the same node.

Think carefully about this test cases and handle them separately and Most important thing in solving graph problem is clearing the whole graph and arrays after each test cases.

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
//bool check(int N,int pos){return (bool)(N & (1<<pos));}
/*------------------------------------------------*/

vector<int>G[10005];
map<string,int>mp;
map<int,string>mp1;

int d[10005];
bool visit[10005];
int dir[10005];
int cnt=0;

int bfs(int src, int dst)
{
queue<int>Q;
d[src]=0;
visit[src]=1;
Q.push(src);
dir[src]=src;
while(!Q.empty())
{
int u=Q.front();
Q.pop();
if(u==dst) return 1;

loop(i,SZ(G[u]))
{
int v=G[u][i];
if(!visit[v])
{
visit[v]=1;
d[v]=d[u]+1;
Q.push(v);
dir[v]=u;
}
}
}
return -1;
}

void path_print(int a, int b)
{
if(a==b) return;
path_print(dir[a],b);
cout<<mp1[dir[a]]<<" "<<mp1[a]<<endl;
}

void allclear(int n)
{
loop(i,n)
{
G[i].clear();
d[i]=visit[i]=dir[i]=0;
}
mp.clear();
mp1.clear();
cnt=0;
}

int main()
{
CIN;
//    freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);
int n;
bool test=0;
while(cin>>n)
{
if(test) cout<<endl;
test=1;
string s1,s2;
loop(i,n)
{
cin>>s1>>s2;
if(mp[s1]==0)
{
mp[s1]= ++cnt;
mp1[cnt]=s1;
}
if(mp[s2]==0)
{
mp[s2]= ++cnt;
mp1[cnt]=s2;
}
G[mp[s1]].pb(mp[s2]);
G[mp[s2]].pb(mp[s1]);
}

cin>>s1>>s2;
if(s1==s2)
cout<<s1<<" "<<s1<<endl;
else if((mp[s1]==0 || mp[s2]==0))
{
cout<<"No route"<<endl;
}
else if(bfs(mp[s1],mp[s2])==-1)
cout<<"No route"<<endl;
else
path_print(mp[s2],mp[s1]);

allclear(cnt+5);

}
return 0;
}

```

# USACO: The Castle

0

```
/*
PROG: castle
LANG: C++
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sfl(a)          scanf("%lld",&a)
#define sff(a,b)        scanf("%d %d",&a,&b)
#define sffl(a,b)       scanf("%lld %lld",&a,&b)
#define sfff(a,b,c)     scanf("%d %d %d",&a,&b,&c)
#define sfffl(a,b,c)    scanf("%lld %lld %lld",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<=b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

//int Set(int N,int pos){return N=N | (1<<pos);}
//int reset(int N,int pos){return N= N & ~(1<<pos);}
bool check(int N,int pos)
{
return (bool)(N & (1<<pos));
}
/*------------------------------------------------*/

int graph[52][52];
int dp[2505];
int visited[52][52];

int r,c,s,extend=0;

int dfs(int i, int j, int x)
{
//    if(visited[i][j]) return 0;
visited[i][j]=x;
int d=0;
if(!check(graph[i][j],0) && !visited[i][j-1]) d+=1+dfs(i,j-1,x);
if(!check(graph[i][j],2) && !visited[i][j+1]) d+=1+dfs(i,j+1,x);
if(!check(graph[i][j],1) && !visited[i-1][j]) d+=1+dfs(i-1,j,x);
if(!check(graph[i][j],3) && !visited[i+1][j]) d+=1+dfs(i+1,j,x);
return d;
}

int n,m;

void func(int i, int j,int x)
{
int t=visited[i][j];
int d=0;
if(check(graph[i][j],0) && t!=visited[i][j-1] && j-1>=1)
{
d=dp[t]+dp[visited[i][j-1]];
if(d>extend)
{
extend=d;
r=i,c=j;
s=0;
}
else if(d==extend)
{
if(j<c)
{
r=i,c=j;
s=0;
}
else if(j==c)
{
if(i>r)
{
r=i,j=c;
s=0;
}
}
}
}

if(check(graph[i][j],2) && t!=visited[i][j+1] && j+1<=m)
{
d=dp[t]+dp[visited[i][j+1]];
if(d>extend)
{
extend=d;
r=i,c=j;
s=2;
}
else if(d==extend)
{
if(j<c)
{
r=i,c=j;
s=2;
}
else if(j==c)
{
if(i>r)
{
r=i,j=c;
s=2;
}
else if(i==r)
{
if(s!=1)
{
r=i,j=c;
s=2;
}
}
}
}
}

// if(check(graph[i][j],2) && !visited[i][j+1]) d+=1+dfs(i,j+1,x);
//if(check(graph[i][j],1) && !visited[i-1][j]) d+=1+dfs(i-1,j,x);
if(check(graph[i][j],1) && t!=visited[i-1][j] && i-1>=1)
{
d=dp[t]+dp[visited[i-1][j]];
if(d>extend)
{
extend=d;
r=i,c=j;
s=1;
}
else if(d==extend)
{
if(j<c)
{
r=i,c=j;
s=1;
}
else if(j==c)
{
if(i>r)
{
r=i,j=c;
s=1;
}
else if(i==r)
{
r=i,j=c;
s=1;
}
}
}
}
//if(check(graph[i][j],3) && !visited[i+1][j]) d+=1+dfs(i+1,j,x);

if(check(graph[i][j],3) && t!=visited[i+1][j] && i+1<=n)
{
d=dp[t]+dp[visited[i+1][j]];
if(d>extend)
{
extend=d;
r=i,c=j;
s=3;
}
else if(d==extend)
{
if(j<c)
{
r=i,c=j;
s=3;
}
else if(j==c)
{
if(i>r)
{
r=i,j=c;
s=3;
}
}
}
}
}

int main()
{
freopen("castle.in","r",stdin);
freopen("castle.out","w",stdout);
cin>>n>>m;
swap(n,m);
REP(i,1,n) REP(j,1,m) cin>>graph[i][j];

int k=0;
int ans=-1;
REP(i,1,n) REP(j,1,m)
{
if(!visited[i][j])
{
k++;
dp[k]=dfs(i,j,k)+1;
ans=max(ans,dp[k]);
}
}

cout<<k<<endl<<ans<<endl;
REP(i,1,n) REP(j,1,m)
{
func(i,j,visited[i][j]);
//        cout<<i<<" "<<j<<" "<<extend<<" "<<s<<endl;
}
cout<<extend<<endl;
cout<<r<<" "<<c;
if(s==2)pf(" E\n");
else
pf(" N\n");
return 0;
}

```

# Light OJ : 1168 – Wishing Snake

0

Algorithm :

1. Make a graph from input data and Determine the SCC of the graph.
2. Make a new Graph from SCC. Consider Each SCC as a node of this graph.
3. If any Node of SCC_graph have more than 1 out degree and It is not possible to traverse all node from the SCC which contain’s the node 0 of the input graph then Print “NO”.
4. Otherwise Print “YES”;

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             1005
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

const int fx[]={+1,-1,+0,+0};
const int fy[]={+0,+0,+1,-1};

vector<int>graph[MAX],rev_graph[MAX],scc_graph[MAX];
int visited[MAX];
int node[MAX],scc_num[MAX],node_num,scc;
stack<int>st;
bool test,scc_vis[MAX];

void allclear()
{
loop(i,node_num+2)
{
visited[i]=0;
graph[i].clear();
rev_graph[i].clear();
scc_num[i]=0;
}
loop(i,scc+2)
{
scc_graph[i].clear();
scc_vis[i]=0;
}
node_num=0;
scc=0;
}

void dfs1(int u)
{
visited[u]++;
loop(i,SZ(graph[u]))
{
int v=graph[u][i];
if(visited[v]==0)
dfs1(v);
}
st.push(u);
}

void dfs2(int u)
{
visited[u]++;
scc_num[u]=scc;
loop(i,SZ(rev_graph[u]))
{
int v=rev_graph[u][i];
if(visited[v]!=2)
dfs2(v);
}
}

void dfs3(int u)
{
scc_vis[u]=1;
if(SZ(scc_graph[u])>1)
{test=0;return;}
loop(i,SZ(scc_graph[u]))
dfs3(scc_graph[u][i]);
}

int main()
{
///freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);

int t;
sf(t);
TEST_CASE(t)
{
ms(node,-1);
int n,m,u,v;
node_num=0;
node[0]=node_num;
sf(n);
loop(i,n)
{
sf(m);
loop(j,m)
{
sff(u,v);
if(node[u]==-1) node[u]=++node_num;
if(node[v]==-1) node[v]=++node_num;
graph[node[u]].pb(node[v]);
rev_graph[node[v]].pb(node[u]);
}
}

loop(i,node_num)
{
if(visited[i]==0)
dfs1(i);
}

scc=0;
while(!st.empty())
{
u=st.top();
st.pop();
if(visited[u]!=2)
{
scc++;
dfs2(u);
}
}

loop(i,node_num)
{
loop(j,SZ(graph[i]))
{
u=graph[i][j];
if(scc_num[i]!=scc_num[u])
scc_graph[scc_num[i]].pb(scc_num[u]);
}
}

test=1;
dfs3(scc_num[0]);
if(test)
{
REP(i,1,scc+1)
{
if(!scc_vis[i])
test=0;
}
}
PRINT_CASE;
if(test)
pf("YES\n");
else
pf("NO\n");
allclear();

}
return 0;
}

```

# Light OJ : 1417 – Forwarding Emails

0

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             50005
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

int n,dfsnum,dis[MAX];
vector<int> graph[MAX],rev_graph[MAX];
bool mp[MAX],mp1[MAX],mp2[MAX];

void allclear()
{
loop(i,n+2)
{
graph[i].clear();
rev_graph[i].clear();
dis[i]=0;
mp[i]=mp1[i]=mp2[i]=0;
}
dfsnum=0;
}

void dfs1(int u)
{
mp[u]=1;
dfsnum++;
loop(i,SZ(graph[u]))
{
int v=graph[u][i];
if(!mp[v])
dfs1(v);
}
dis[u]=++dfsnum;
}

void dfs2(int u)
{
mp1[u]=1;
loop(i,SZ(rev_graph[u]))
{
int v=rev_graph[u][i];
if(!mp1[v])
dfs2(v);
}
}

void dfs3(int u)
{
mp2[u]=1;
dfsnum++;
loop(i,SZ(graph[u]))
{
int v=graph[u][i];
if(!mp2[v])
dfs3(v);
}
}

void dfs4(int u)
{
mp2[u]=0;
loop(i,SZ(graph[u]))
{
int v=graph[u][i];
if(mp2[v])
dfs4(v);
}
}

int main()
{
///freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);

int t;
sf(t);
TEST_CASE(t)
{
sf(n);
allclear();
int a,b;
loop(i,n)
{
sff(a,b);
graph[a].pb(b);
rev_graph[b].pb(a);
}
REP(i,1,n+1)
{
if(!mp[i])
dfs1(i);
}

vector<pii>top_sort;
REP(i,1,n+1)
{
top_sort.pb(MP(dis[i],i));
}

sort(top_sort.rbegin(),top_sort.rend());
vector<int>scc;

loop(i,SZ(top_sort))
{
int u=top_sort[i].ss;
if(!mp1[u])
{
scc.pb(u);
dfs2(u);
}
}

top_sort.clear();
loop(i,SZ(scc))
{
int u=scc[i];
if(!mp2[u])
{
dfsnum=0;
dfs3(u);
top_sort.pb(MP(dfsnum,u));
dfs4(u); // this DFS is clearing only visited node.
}
}

sort(top_sort.rbegin(),top_sort.rend());
PRINT_CASE;
if(SZ(top_sort)==1)
pf("%d\n",top_sort[0].ss);
else
{
loop(i,SZ(top_sort)-1)
{
if(top_sort[i].ff!=top_sort[i+1].ff) // This is for determine the smallest one.
{
pf("%d\n",top_sort[i].ss);
break;
}
}
}
}
return 0;
}

```

# Light OJ : 1406 – Assassin`s Creed

0

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             10000
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

vector<int>graph[16];
bool visited[16][1<<16];
bool check_vis[1<<16];
int dp[1<<16];
int n,m;

{
loop(i,SZ(graph[u]))
{
int v=graph[u][i];
}
}

void allclear()
{
loop(i,n+1)
{
graph[i].clear();
}
ms(visited,0);
ms(check_vis,0);
ms(dp,-1);
}

{
if(ret!=-1) return ret;
ret=100;
{
if(check_vis[i])
{
ret=min(ret,1+dp_func(mask^i)); // XOR for remaining unvisited node
}
}
return ret;
}

int main()
{
///freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);
int t,a,b;
sf(t);
TEST_CASE(t)
{
sff(n,m);
allclear();
loop(i,m)
{
sff(a,b);
a--,b--;
graph[a].pb(b);
}

loop(i,n)
{
dfs(i,1<<i);
}
PRINT_CASE;
cout<<dp_func((1<<n)-1)<<endl;
}
return 0;
}

```

# Light OJ 1063 – Ant Hills

0

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             100007
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

vector<int>graph[MAX];
int n,m,cnt;
bool visited[MAX],artpoint[MAX];
int back_edge[MAX],dis[MAX],degroot,dfsnum,root;

void dfs(int u)
{
visited[u]=1;
dfsnum++;
back_edge[u]=dis[u]=dfsnum;
loop(i,SZ(graph[u]))
{
int v=graph[u][i];
if(!visited[v])
{
dfs(v);
if(u==root) degroot++;
if(degroot>=2)
{
artpoint[root]=1;
}

back_edge[u]=min(back_edge[u],back_edge[v]);
if(back_edge[v]>=dis[u] && u!=root)
{
artpoint[u]=1;
}

}
else
back_edge[u]=min(back_edge[u],dis[v]);
}
}

void allclear()
{
loop(i,n+5)
{
graph[i].clear();
visited[i]=0;
artpoint[i]=0;
back_edge[i]=0;
dis[i]=0;
}
cnt=dfsnum=degroot=0;
}

int main()
{
///freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);
int t;
sf(t);
TEST_CASE(t)
{
sff(n,m);
allclear();
int a,b;
loop(i,m)
{
sff(a,b);
graph[a].pb(b);
graph[b].pb(a);
}

root=1;
dfs(1);

REP(i,1,n+1)
if(artpoint[i]) cnt++;
PRINT_CASE;
cout<<cnt<<endl;
}
return 0;
}

```

# Light OJ 1108 – Instant View of Big Bang

0

Algorithm:

1. Make a graph by reverse the edge direction.
2. Run Bellman Ford in reverse Graph and check if there exist a negative weight cycle. Reversing edge doesn’t affect in cycle because if we reverse the edge direction then cycle remain unchanged.
3. If exist a negative cycle then run a DFS on the reverse graph for finding the nodes which are reachable from negative cycle and store them in a vector and after sorting the vector print them.
4. If there is no negative cycle then print impossible.

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             1005
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

struct data
{
int u,v,w;
data(int x, int y, int z)
{
u=x,v=y,w=z;
}
};

int n,m,total_edge;
vector<data> graph;
vector<int>ans,reverse_graph[MAX];
map<int,bool>mp;
int d[MAX];
bool visited[MAX];

void dfs(int u)
{
mp[u]=1;
ans.pb(u);
loop(i,SZ(reverse_graph[u]))
{
int v=reverse_graph[u][i];
if(!mp[v])
dfs(v);
}
}

bool bellmanford()
{
for(int i=1;i<n;i++)
{
loop(i,m)
{
int u=graph[i].u;
int v=graph[i].v;
if(d[u]+graph[i].w<d[v])
{
d[v]=d[u]+graph[i].w;
}
}
}

bool negative_cycle=0;

loop(i,m)
{
int u=graph[i].u;
int v=graph[i].v;
if(d[u]+graph[i].w<d[v])
{
negative_cycle=1;
d[v]=d[u]+graph[i].w;
if(!mp[u])
dfs(u);
}
}
return negative_cycle;
}

void allclear()
{
graph.clear();
ans.clear();
mp.clear();

loop(i,n+2)
{d[i]=inf;reverse_graph[i].clear();}
}

int main()
{
///freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);
int t;
sf(t);
TEST_CASE(t)
{
int u,v,w;
sff(n,m);
allclear();
loop(i,m)
{
sfff(u,v,w);
graph.pb(data(v,u,w));//reversing graph
reverse_graph[v].pb(u);
}

PRINT_CASE;
if(bellmanford())
{
sort(all(ans));
pf("%d",ans[0]);
REP(i,1,SZ(ans))
pf(" %d",ans[i]);
pf("\n");
}
else
pf("impossible\n");
}
return 0;
}

```

# Light OJ 1221 – Travel Company (Bellman Ford)

1

```
/*
+-+ +-+ +-+
|R| |.| |S|
+-+ +-+ +-+
*/

#include <bits/stdc++.h>

#define pii             pair <int,int>
#define sc              scanf
#define pf              printf
#define Pi              2*acos(0.0)
#define ms(a,b)         memset(a, b, sizeof(a))
#define pb(a)           push_back(a)
#define MP              make_pair
#define db              double
#define ll              long long
#define EPS             10E-10
#define ff              first
#define ss              second
#define sqr(x)          (x)*(x)
#define D(x)            cout<<#x " = "<<(x)<<endl
#define VI              vector <int>
#define DBG             pf("Hi\n")
#define MOD             100007
#define MAX             105
#define CIN             ios_base::sync_with_stdio(0)
#define SZ(a)           (int)a.size()
#define sf(a)           scanf("%d",&a)
#define sff(a,b)        scanf("%d%d",&a,&b)
#define sfff(a,b,c)     scanf("%d%d%d",&a,&b,&c)
#define loop(i,n)       for(int i=0;i<n;i++)
#define REP(i,a,b)      for(int i=a;i<b;i++)
#define TEST_CASE(t)    for(int z=1;z<=t;z++)
#define PRINT_CASE      printf("Case %d: ",z)
#define all(a)          a.begin(),a.end()
#define intlim          2147483648
#define inf             1000000
#define ull             unsigned long long

using namespace std;

vector<int>from,to,cost;
int d[MAX];

int main()
{
///freopen("in.txt","r",stdin);
///freopen("out.txt","w",stdout);
int t;
sf(t);
TEST_CASE(t)
{
int n,r,p;
sfff(n,r,p);
int a,b,income,expence;
loop(i,r)
{
sc("%d %d %d %d",&a,&b,&income,&expence);
from.pb(a);
to.pb(b);
cost.pb(p*expence-income);
}

bool test=0;
for(int j=1;j<=n;j++)
{
for(int i=0;i<r;i++)
{
int temp=d[from[i]]+cost[i];
if(temp<d[to[i]])
{
if(j==n) test=1;
d[to[i]]=temp;
}
}
}

PRINT_CASE;
if(test)
pf("YES\n");
else
pf("NO\n");

ms(d,0);
from.clear();
to.clear();
cost.clear();
}
return 0;
}

```

This problem can be solved using Floyed Warshal algorithm. Another solution is Here Light OJ 1221 – Travel Company (Floyed Warshal)