Nice tutorial :- tushar roy
Link:- https://www.youtube.com/watch?v=RpgcYiky7uw&t=849s
1 no:- uva 247 no problem code (by mine)
#include<bits/stdc++.h>
#define mx 105
using namespace std;
vector<int>vec[mx],ultavec[mx];
vector<string>allnames;
vector<int>dhokalam;
map<string,int>mp;
int vis[mx],ar[mx],newline=0,cs=1,n,m;
void dfs(int u)
{
vis[u]=1;
int v,j;
for(j=0;j<vec[u].size();j++)
{
v=vec[u][j];
if(vis[v]==0)
{
dfs(v);
}
}
dhokalam.push_back(u);
}
void dfs2(int u,int c)
{
vis[u]=0;
int v,j;
ar[u]=c;
for(j=0;j<ultavec[u].size();j++)
{
v=ultavec[u][j];
if(vis[v]==1)
{
dfs2(v,c);
}
}
}
void print(int len)
{
if(newline!=0)
printf("\n");
newline=1;
int i1,j;
int spc=0;
printf("Calling circles for data set %d:\n",cs++);
for(i1=1;i1<=len;i1++)
{
spc=0;
for(j=1;j<=n;j++)
{
if(ar[j]==i1)
{
if(spc==1)
{
printf(", ");
}
spc=1;
cout<<allnames[j-1];
}
}
printf("\n");
}
}
main()
{
while(cin>>n>>m)
{
if ( n == 0 && m == 0 ) break;
int i,cnt=1;;
for(i=0;i<=mx;i++)
{
vec[i].clear();
ultavec[i].clear();
}
allnames.clear();
mp.clear();
newline=0;
string s,s1;
for(i=1;i<=m;i++)
{
cin>>s>>s1;
if(mp[s]==0)
{
mp[s]=cnt++;
allnames.push_back(s);
}
if(mp[s1]==0)
{
mp[s1]=cnt++;
allnames.push_back(s1);
}
vec[mp[s]].push_back(mp[s1]);
ultavec[mp[s1]].push_back(mp[s]);
}
for(i=1;i<cnt;i++)
{
if(vis[i]==0)
{
dfs(i);
}
}
int k=dhokalam.size()-1;
cnt=0;
for(i=k;i>=0;i--)
{
if(vis[dhokalam[i]]==1)
{
dfs2(dhokalam[i],++cnt);
}
}
print(cnt);
}
}
2 no: uva 247 no problem code (from internet)
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define N 100
using namespace std;
map<string, int> names;
vector<string> rNames;
vector <int> edges [N];
vector <int> rEdges [N]; // reversed edges
vector <int> sortedNode;
bool vis [N];
int comp [N]; // component number of a node
int cases = 0;
bool blank = false;
int n, m;
void reset ()
{
int i;
for (i = 0; i < N; i++ )
{
edges [i].clear();
rEdges [i].clear();
}
sortedNode.clear();
names.clear();
rNames.clear();
memset (vis, false, sizeof vis);
}
void dfs1 (int x)
{
vis [x] = true;
int u;
for (u = 0; u < edges [x].size(); u++ )
{
if (vis[edges[x][u]]==0)
dfs1(edges [x] [u]);
}
sortedNode.push_back(x);
}
void dfs2 (int x, int c)
{
vis [x] = false;
comp [x] = c;
int u;
for (u = 0; u < rEdges [x].size(); u++ )
{
if (vis[rEdges [x][u]])
dfs2(rEdges [x] [u], c);
}
}
void printOutput(int compLen)
{
if (blank) printf ("\n");
blank = true;
printf ("Calling circles for data set %d:\n", ++cases);
bool space;
int i,j;
for (i = 1; i <= compLen; i++ )
{
space = false;
for (j=0;j<n;j++)
{
if (comp [j + 1] == i)
{
if (space) printf (", ");
space = true;
cout << rNames[j];
}
}
printf ("\n");
}
}
int main ()
{
while (scanf ("%d %d", &n, &m))
{
if ( n == 0 && m == 0 ) break;
reset();
int i,namesLen=0;
string name1, name2;
for(i=0;i<m;i++)
{
cin >> name1 >> name2;
if (names [name1]==0)
{
++namesLen;
names [name1] = namesLen;
rNames.push_back(name1);
}
if (names [name2]==0)
{
++namesLen;
names [name2] = namesLen;
rNames.push_back(name2);
}
edges [names [name1]].push_back(names [name2]);
rEdges [names [name2]].push_back(names [name1]);
}
for(i=0;i<namesLen;i++)
{
if (!vis [i + 1])
{
dfs1(i + 1);
}
}
int compId = 0;
for(i=sortedNode.size()-1;i>=0;i--)
{
if ( vis [sortedNode [i]] )
dfs2(sortedNode [i], ++compId);
}
printOutput(compId);
}
return 0;
}
Link:- https://www.youtube.com/watch?v=RpgcYiky7uw&t=849s
1 no:- uva 247 no problem code (by mine)
#include<bits/stdc++.h>
#define mx 105
using namespace std;
vector<int>vec[mx],ultavec[mx];
vector<string>allnames;
vector<int>dhokalam;
map<string,int>mp;
int vis[mx],ar[mx],newline=0,cs=1,n,m;
void dfs(int u)
{
vis[u]=1;
int v,j;
for(j=0;j<vec[u].size();j++)
{
v=vec[u][j];
if(vis[v]==0)
{
dfs(v);
}
}
dhokalam.push_back(u);
}
void dfs2(int u,int c)
{
vis[u]=0;
int v,j;
ar[u]=c;
for(j=0;j<ultavec[u].size();j++)
{
v=ultavec[u][j];
if(vis[v]==1)
{
dfs2(v,c);
}
}
}
void print(int len)
{
if(newline!=0)
printf("\n");
newline=1;
int i1,j;
int spc=0;
printf("Calling circles for data set %d:\n",cs++);
for(i1=1;i1<=len;i1++)
{
spc=0;
for(j=1;j<=n;j++)
{
if(ar[j]==i1)
{
if(spc==1)
{
printf(", ");
}
spc=1;
cout<<allnames[j-1];
}
}
printf("\n");
}
}
main()
{
while(cin>>n>>m)
{
if ( n == 0 && m == 0 ) break;
int i,cnt=1;;
for(i=0;i<=mx;i++)
{
vec[i].clear();
ultavec[i].clear();
}
allnames.clear();
mp.clear();
newline=0;
string s,s1;
for(i=1;i<=m;i++)
{
cin>>s>>s1;
if(mp[s]==0)
{
mp[s]=cnt++;
allnames.push_back(s);
}
if(mp[s1]==0)
{
mp[s1]=cnt++;
allnames.push_back(s1);
}
vec[mp[s]].push_back(mp[s1]);
ultavec[mp[s1]].push_back(mp[s]);
}
for(i=1;i<cnt;i++)
{
if(vis[i]==0)
{
dfs(i);
}
}
int k=dhokalam.size()-1;
cnt=0;
for(i=k;i>=0;i--)
{
if(vis[dhokalam[i]]==1)
{
dfs2(dhokalam[i],++cnt);
}
}
print(cnt);
}
}
#include<bits/stdc++.h>
#include<bits/stdc++.h>
#define N 100
using namespace std;
map<string, int> names;
vector<string> rNames;
vector <int> edges [N];
vector <int> rEdges [N]; // reversed edges
vector <int> sortedNode;
bool vis [N];
int comp [N]; // component number of a node
int cases = 0;
bool blank = false;
int n, m;
void reset ()
{
int i;
for (i = 0; i < N; i++ )
{
edges [i].clear();
rEdges [i].clear();
}
sortedNode.clear();
names.clear();
rNames.clear();
memset (vis, false, sizeof vis);
}
void dfs1 (int x)
{
vis [x] = true;
int u;
for (u = 0; u < edges [x].size(); u++ )
{
if (vis[edges[x][u]]==0)
dfs1(edges [x] [u]);
}
sortedNode.push_back(x);
}
void dfs2 (int x, int c)
{
vis [x] = false;
comp [x] = c;
int u;
for (u = 0; u < rEdges [x].size(); u++ )
{
if (vis[rEdges [x][u]])
dfs2(rEdges [x] [u], c);
}
}
void printOutput(int compLen)
{
if (blank) printf ("\n");
blank = true;
printf ("Calling circles for data set %d:\n", ++cases);
bool space;
int i,j;
for (i = 1; i <= compLen; i++ )
{
space = false;
for (j=0;j<n;j++)
{
if (comp [j + 1] == i)
{
if (space) printf (", ");
space = true;
cout << rNames[j];
}
}
printf ("\n");
}
}
int main ()
{
while (scanf ("%d %d", &n, &m))
{
if ( n == 0 && m == 0 ) break;
reset();
int i,namesLen=0;
string name1, name2;
for(i=0;i<m;i++)
{
cin >> name1 >> name2;
if (names [name1]==0)
{
++namesLen;
names [name1] = namesLen;
rNames.push_back(name1);
}
if (names [name2]==0)
{
++namesLen;
names [name2] = namesLen;
rNames.push_back(name2);
}
edges [names [name1]].push_back(names [name2]);
rEdges [names [name2]].push_back(names [name1]);
}
for(i=0;i<namesLen;i++)
{
if (!vis [i + 1])
{
dfs1(i + 1);
}
}
int compId = 0;
for(i=sortedNode.size()-1;i>=0;i--)
{
if ( vis [sortedNode [i]] )
dfs2(sortedNode [i], ++compId);
}
printOutput(compId);
}
return 0;
}
কোন মন্তব্য নেই:
একটি মন্তব্য পোস্ট করুন