Pagini recente » Cod sursa (job #1033900) | Cod sursa (job #1670172) | Cod sursa (job #852959) | Cod sursa (job #884915) | Cod sursa (job #880887)
Cod sursa(job #880887)
#include<fstream>
#include<vector>
#include<stack>
#define vec G[nod][i]
#define vec_GT GT[nod][i]
#define NMAX 100005
using namespace std;
int n,m,c;
vector<int> G[NMAX],GT[NMAX],sol[NMAX];
stack<int> S;
bool use[NMAX],use_GT[NMAX];
void read()
{
ifstream fin("ctc.in");
fin>>n>>m;
int x,y;
for(int i=0;i<m;i++)
{
fin>>x>>y;
G[x].push_back(y);
GT[y].push_back(x);
}
fin.close();
}
void DFS_stack(int nod)
{
use[nod]=1;
for(size_t i=0;i<G[nod].size();i++)
if(!use[vec])
DFS_stack(vec);
S.push(nod);
}
void DFS_ctc(int nod)
{
use_GT[nod]=1;
for(size_t i=0;i<GT[nod].size();i++)
if(!use_GT[vec_GT])
DFS_ctc(vec_GT);
sol[c].push_back(nod);
}
void print()
{
ofstream fout("ctc.out");
fout<<c<<'\n';
for(int nod=0;nod<c;nod++,fout<<'\n')
for(size_t i=0;i<sol[nod].size();i++)
fout<<sol[nod][i]<<' ';
fout.close();
}
int main()
{
read();
for(int i=1;i<=n;i++)
if(!use[i])
DFS_stack(i);
for(;!S.empty();S.pop())
if(!use_GT[S.top()])
{
DFS_ctc(S.top());
c++;
}
print();
return 0;
}