Pagini recente » Borderou de evaluare (job #3098749) | Borderou de evaluare (job #1646489) | Borderou de evaluare (job #1036418) | Borderou de evaluare (job #3098729) | Cod sursa (job #941069)
Cod sursa(job #941069)
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m, x, y, nrCtc;
vector<int>g[100001], gt[100001], c[100001];
vector<int>discovered;
bool vis[100001];
void Dfs(int x)
{
if(vis[x]) return;
vis[x]=true;
for(vector<int>::iterator it=g[x].begin(); it<g[x].end(); it++ )
Dfs(*it);
discovered.push_back(x);
}
void Dfs2(int x)
{
if(vis[x]) return;
vis[x]=true;
for(vector<int>::iterator it=gt[x].begin(); it<gt[x].end(); it++ )
Dfs2(*it);
c[nrCtc].push_back(x);
}
int main()
{
fin>>n>>m;
for(int i = 1; i<= m; i++ )
{
fin>>x>>y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 1; i<= n; i++ )
Dfs(i);
memset(vis,0,sizeof(vis));
for(;discovered.size();discovered.pop_back())
if( !vis[discovered.back()] )
{
nrCtc++;
Dfs2(discovered.back());
}
fout<<nrCtc << '\n';
for(int i = 1; i<= nrCtc; i++ )
{
sort(c[i].begin(),c[i].end());
for(vector<int>::iterator it=c[i].begin(); it<c[i].end(); it++)
fout<<*it<<' ';
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}