Pagini recente » Cod sursa (job #892492) | Cod sursa (job #1279739) | Statistici Negru Radu-Andrei (rneg2001rei) | Cod sursa (job #394421) | Cod sursa (job #2140798)
#include <fstream>
#include <cstring>
#include <vector>
#define nmax 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int viz[nmax], st[nmax];
int sol, n, m, i, j, x, y;
vector <int> g[nmax], gt[nmax], ctc[nmax];
vector <int> :: iterator it;
inline void dfs (int nod)
{
int i;
viz[nod] = 1;
for (i=0; i < g[nod].size (); i++)
{
if(!viz[g[nod][i]])
dfs (g[nod][i]);
}
st[++st[0]] = nod;
}
inline void dfst (int nod)
{
int i;
viz[nod] = 1;
for (i=0; i < gt[nod].size(); i++)
{
if(!viz[gt[nod][i]])
dfst (gt[nod][i]);
}
ctc[sol].push_back (nod);
}
int main()
{
fin>>n>>m;
for (i = 1; i <= m; i++)
{
fin >> x >> y;
g[x].push_back(y);
gt[y].push_back(x);
}
memset(st, 0, sizeof (st));
memset(viz, 0, sizeof (viz));
for (i = 1; i <= n; i++)
{
if(!viz[i])
dfs (i);
}
memset(viz, 0, sizeof(viz));
for (i = n; i > 0; i--)
{
if(!viz[st[i]])
{
sol++;
dfst (st[i]);
}
}
fout << sol << '\n';
for (i = 1; i <= sol; i++)
{
for (j=0; j < ctc[i].size(); j++)
fout << ctc[i][j]<<" ";
fout<<'\n';
}
fin.close();
fout.close();
return 0;
}