Pagini recente » Cod sursa (job #2137633) | Cod sursa (job #2688239) | Cod sursa (job #1148041) | Cod sursa (job #1272628) | Cod sursa (job #1140904)
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
#define nr 100001
vector<int>normal[nr],transpus[nr],raspuns[nr];
bool viz[nr];
int vecini[nr],nr_vecini=0,nr_elemente;
void dfs1(int start)
{
viz[start]=1;
for(int i=0; i<normal[start].size(); i++)
{
if(!viz[normal[start][i]])
dfs1(normal[start][i]);
}
vecini[nr_vecini++]=start;
}
void dfs2(int start)
{
viz[start]=0;
raspuns[nr_elemente].push_back(start);
for(int i=0; i<transpus[start].size(); i++)
if(viz[transpus[start][i]])
dfs2(transpus[start][i]);
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m;
f>>n>>m;
for(int i=1; i<=m; i++)
{
int a,b;
f>>a>>b;
normal[a].push_back(b);
transpus[b].push_back(a);
}
for(int i=1; i<=n; i++)
{
if(!viz[i])
{
dfs1(i);
}
}
while(nr_vecini--)
{
if(viz[vecini[nr_vecini]])
{
nr_elemente++;
dfs2(vecini[nr_vecini]);
}
}
g<<nr_elemente<<"\n";
for(int i=1; i<=nr_elemente; i++)
{
for(int j=0; j<raspuns[i].size(); j++)
g<<raspuns[i][j]<<" ";
g<<"\n";
}
}