Pagini recente » Cod sursa (job #3177363) | Cod sursa (job #2658586) | Cod sursa (job #700590) | Cod sursa (job #590346) | Cod sursa (job #2870102)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int x,y,n,m,i,comp;
bitset<100002> fr;
vector<int> g[100002],ginv[100002],da[100002],S;
void dfs(int start)
{
fr[start]=1;
for(auto x:g[start])
if(fr[x]==0)
dfs(x);
S.push_back(start);
}
void dfsinv(int start)
{
da[comp].push_back(start);
fr[start]=1;
for(auto x:ginv[start])
if(fr[x]==0)
dfsinv(x);
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>x>>y;
g[x].push_back(y);
ginv[y].push_back(x);
}
for(i=1;i<=n;i++)
if(fr[i]==0)
dfs(i);
for(i=1;i<=n;i++)
fr[i]=0;
for(i=S.size()-1;i>=0;i--)
{
if(fr[S[i]]==0)
{
comp++;
dfsinv(S[i]);
}
}
fout<<comp<<'\n';
for(i=1;i<=comp;i++)
{
for(auto j:da[i])
fout<<j<<' ';
fout<<'\n';
}
return 0;
}