Pagini recente » Cod sursa (job #2695817) | Cod sursa (job #1509716) | Cod sursa (job #396781) | Cod sursa (job #562670) | Cod sursa (job #1328553)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
int N,M,u;
vector<int> s[100005],p[100005],sol[100005];
queue<int> q;
bool viz[100005];
int pp[100005],mm[100005];
void latime_plus(int i);
void latime_minus(int i);
int main()
{
in>>N>>M;
int i,j,a,b;
for(i=1;i<=N;++i) s[i].push_back(0),p[i].push_back(0);
for(i=1;i<=M;++i)
{
in>>a>>b;
s[a].push_back(b);
s[a][0]++;
p[b].push_back(a);
p[b][0]++;
}
for(i=1;i<=N;++i)
{
if(!viz[i])
{
++u;
sol[u].push_back(0);
latime_plus(i);
latime_minus(i);
}
}
out<<u<<'\n';
for(i=1;i<=u;++i)
{
for(j=1;j<=sol[i][0];++j)
out<<sol[i][j]<<' ';
out<<'\n';
}
}
void latime_plus(int i)
{
q.push(i);
pp[i]=i;
int j,c;
while(!q.empty())
{
c=q.front();
q.pop();
for(j=1;j<=s[c][0];++j)
{
if(pp[s[c][j]]!=i)
{
pp[s[c][j]]=i;
q.push(s[c][j]);
}
}
}
}
void latime_minus(int i)
{
q.push(i);
mm[i]=i;
if(pp[i]==i)
sol[u].push_back(i),sol[u][0]++;
int j,c;
while(!q.empty())
{
c=q.front();
q.pop();
for(j=1;j<=p[c][0];++j)
{
if(mm[p[c][j]]!=i)
{mm[p[c][j]]=i;
if(pp[p[c][j]]==i) sol[u].push_back(p[c][j]),sol[u][0]++,viz[p[c][j]]=1;
q.push(p[c][j]);}
}
}
}