Pagini recente » Cod sursa (job #251502) | Cod sursa (job #3310752) | Diferente pentru problema/arbquery intre reviziile 3 si 4 | Atasamentele paginii Profil shaghi | Cod sursa (job #3336085)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,nrctc;
vector<int>CTC[100001],V[100001],VT[100001];
stack<int>st;
bool viz1[100001],viz2[100001];
void dfs1(int x)
{
viz1[x]=1;
for(auto&it:V[x])
if(!viz1[it])
dfs1(it);
st.push(x);
}
void dfs2(int x)
{
viz2[x]=1;
CTC[nrctc].push_back(x);
for(auto&it:VT[x])
if(!viz2[it])
dfs2(it);
}
int main()
{
int x,y;
fin>>n>>m;
for(int i=1;i<=m;i++)
{
fin>>x>>y;
V[x].push_back(y);
VT[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!viz1[i])
dfs1(i);
while(st.size())
{
if(!viz2[st.top()])
{
nrctc++;
dfs2(st.top());
}
st.pop();
}
fout<<nrctc<<'\n';
for(int i=1;i<=nrctc;i++)
{
for(auto&it:CTC[i])
fout<<it<<' ';
fout<<'\n';
}
return 0;
}