Pagini recente » Cod sursa (job #3234848) | Cod sursa (job #2843124) | Cod sursa (job #2125481) | Cod sursa (job #477975) | Cod sursa (job #1525352)
#include <fstream>
#include <vector>
#include <queue>
#define w 250
using namespace std;
struct con {int v;bool sens;};
vector <con> a[w];
queue <int> q;
vector <int> l[20];
bool up[w],um[w],viz[w];
void bfs(int xx)
{
int x,i;
con y;
q.push(xx);
while(!q.empty())
{
x=q.front();
q.pop();
for (i=0;i<=a[x].size()-1;i++)
{
y=a[x][i];
if ((!up[y.v])&&y.sens)
{
up[y.v]=1;
q.push(y.v);
}
}
}
q.push(xx);
while(!q.empty())
{
x=q.front();
q.pop();
for (i=0;i<=a[x].size()-1;i++)
{
y=a[x][i];
if ((!um[y.v])&&(!y.sens))
{
um[y.v]=1;
q.push(y.v);
}
}
}
}
int main()
{
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,i,j,x,y,nr=0;
f>>n>>m;
con r;
for (i=1;i<=m;i++)
{
f>>x>>y;
r.v=y;r.sens=1;
a[x].push_back(r);
r.v=x;r.sens=0;
a[y].push_back(r);
}
for (x=1;x<=n;x++)
{
if (!viz[x])
{
nr++;
up[x]=1;um[x]=1;
bfs(x);
for (i=1;i<=n;i++)
{
if (up[i]&&um[i])
{
viz[i]=1;
l[nr].push_back(i);
}
up[i]=um[i]=0;
}
}
}
g<<nr<<'\n';
for (i=1;i<=nr;i++)
{
for (j=0;j<=l[i].size()-1;j++)
{
g<<l[i][j]<<' ';
}
g<<'\n';
}
f.close();
g.close();
return 0;
}