Pagini recente » Cod sursa (job #2787968) | Cod sursa (job #1134334) | Cod sursa (job #785630) | Istoria paginii runda/simple_oni_sim/clasament | Cod sursa (job #2344304)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
struct nod{ int canBeReached, canReach;
vector<int> toNodes;
vector<int> fromNodes;
bool used;
}p[100003];
int n, m;
vector< vector<int> > Sol;
void MarkNodesPlus(int x=1, int Marker=1)
{
if(p[x].canBeReached!=Marker)
{
p[x].canBeReached=Marker;
for(int i=0;i<p[x].toNodes.size();++i)
MarkNodesPlus(p[x].toNodes[i], Marker);
}
}
void MarkNodesMinus(int x=1, int Marker=1)
{
if(p[x].canReach!=Marker)
{
p[x].canReach=Marker;
for(int i=0;i<p[x].fromNodes.size();++i)
MarkNodesMinus(p[x].fromNodes[i], Marker);
}
}
void add(vector<int> &vec, int x, int t)
{
if(p[x].canReach==t&&p[x].canBeReached==t&&!p[x].used)
{
vec.push_back(x);
p[x].used=1;
for(int i=0;i<p[x].toNodes.size();++i)
add(vec, p[x].toNodes[i], t);
}
}
vector<int> findStrongConexComponent(int x)
{
vector<int> StrongConexComponent;
StrongConexComponent.clear();
MarkNodesPlus(x, x);
MarkNodesMinus(x, x);
add(StrongConexComponent, x, x);
return StrongConexComponent;
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;++i)
{
int x, y;
fin>>x>>y;
p[x].toNodes.push_back(y);
p[y].fromNodes.push_back(x);
}
for(int i=1;i<=n;++i)
{
if(!p[i].used) Sol.push_back(findStrongConexComponent(i));
}
fout<<Sol.size()<<"\n";
for(int i=0;i<Sol.size();++i)
{
for(int j=0;j<Sol[i].size();++j)
fout<<Sol[i][j]<<" ";
fout<<"\n";
}
return 0;
}