Pagini recente » Cod sursa (job #880169) | Cod sursa (job #854010) | Cod sursa (job #1150856) | Cod sursa (job #1292735) | Cod sursa (job #1179528)
#include<fstream>
#include<vector>
#include<bitset>
#include<stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n,m,pos,str;
vector<int>vin[100005];
vector<int>pleaca[100005];
vector<int>componente[100005];
stack<int>S;
bitset<100005>viz;
inline void Citire()
{
int i,x,y;
fin>>n>>m;
for (i=1;i<=m;i++)
{
fin>>x>>y;
pleaca[x].push_back(y);
vin[y].push_back(x);
}
}
inline void DFS(int x)
{
int i,len;
viz[x]=1;
len=pleaca[x].size();
for (i=0;i<len;i++)
if (!viz[pleaca[x][i]])
DFS(pleaca[x][i]);
S.push(x);
}
inline void DFS_t(int x)
{
int i,len;
viz[x]=1;
len=vin[x].size();
componente[str].push_back(x);
for (i=0;i<len;i++)
if (!viz[vin[x][i]])
DFS_t(vin[x][i]);
}
inline void Parcurgere()
{
int i;
for (i=1;i<=n;i++)
if (!viz[i])
DFS(i);
}
inline void Parcurgere_t()
{
int i;
for (i=1;i<=n;i++) viz[i]=0;
while (!S.empty())
{
if (viz[S.top()]==0)
{
str++;
DFS_t(S.top());
}
S.pop();
}
}
inline void Afisare()
{
int i,j,len;
fout<<str<<"\n";
for (i=1;i<=str;i++)
{
len=componente[i].size();
for (j=0;j<len;j++)
fout<<componente[i][j]<<" ";
fout<<"\n";
}
}
int main()
{
Citire();
Parcurgere();
Parcurgere_t();
Afisare();
return 0;
}