Pagini recente » Borderou de evaluare (job #2149462) | Cod sursa (job #871407) | Clasament aventurile_dariei_si_ale_lui_zeebah | Borderou de evaluare (job #2010434) | Cod sursa (job #1094905)
#include <fstream>
#include <vector>
using namespace std;
int k=0, nr_tare_conexe=0;
int vis[50001];
vector <int> ord;
vector <int> rasp[50001];
void dfs(int nod, vector <int> a[], int n){
vis[nod]=1;
int i;
for (i=0; i<a[nod].size(); i++){
if (vis[a[nod][i]]==0){dfs(a[nod][i], a, n);}
}
ord.push_back(nod);
}
void dfs2(int nod, vector <int> a[], int n){
vis[nod]=1;
int i;
for (i=0; i<a[nod].size(); i++){
if (vis[a[nod][i]]==0){dfs2(a[nod][i], a, n);}
}
rasp[nr_tare_conexe].push_back(nod);
}
int main()
{
ifstream in("ctc.in");
ofstream out("ctc.out");
int n, m, e1, e2, i, j;
in>>n>>m;
vector <int> a[n+1];
for (i=1; i<=m; i++){
in>>e1>>e2;
a[e2].push_back(e1);
}
for (i=1; i<=n; i++){
vis[i]=0;
}
for (i=1; i<=n; i++){
if(vis[i]==0){dfs(i, a, n);}
}
for (i=0; i<=n; i++){
vis[i]=0;
}
for (i=0; i<n; i++){
if(vis[ord[i]]==0){dfs2(ord[i], a, n); nr_tare_conexe++;}
}
out<<nr_tare_conexe<<endl;
for (i=0; i<nr_tare_conexe; i++){
for (j=0; j<rasp[i].size(); j++){
out<<rasp[i][j]<<" ";
}
out<<endl;
}
return 0;
}