Pagini recente » Cod sursa (job #808278) | Cod sursa (job #833854) | Cod sursa (job #2386422) | Cod sursa (job #1932304) | Cod sursa (job #1814017)
#include <fstream>
#include <vector>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int Max = 100010;
vector<int> g[Max],gt[Max];
vector<vector<int> > comp;
int q[Max],nr;
char vaz[Max];
void dfs1(int nod)
{
vaz[nod] = 1;
for(vector<int>::iterator it = g[nod].begin(); it != g[nod].end(); it++)
if(!vaz[*it])
dfs1(*it);
q[++nr] = nod;
}
void dfs2(int nod,vector<int> &comp)
{
vaz[nod] = 0;
comp.push_back(nod);
for(vector<int>::iterator it = gt[nod].begin(); it != gt[nod].end(); it++)
if(vaz[*it])
dfs2(*it,comp);
}
int main()
{
int n,m,x,y;
in >> n >> m;
for(int i = 1; i <= m; i++)
{
in >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
for(int i = 1; i <= n; i++)
if(!vaz[i])
dfs1(i);
for(int i = nr; i; i--)
if(vaz[q[i]])
{
comp.push_back(vector<int>());
dfs2(q[i],comp.back());
}
out << comp.size() << "\n";
for(int i = 0; i < comp.size(); i++)
{
for(int j = 0; j < comp[i].size(); j++)
out << comp[i][j] << " ";
out << "\n";
}
return 0;
}