Pagini recente » Cod sursa (job #2780629) | Cod sursa (job #555190) | Cod sursa (job #1366742) | Cod sursa (job #237208) | Cod sursa (job #2220310)
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100005
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v1[Nmax], v2[Nmax], v3[Nmax];
int seen[Nmax];
stack <int> st;
int n, m, x, y;
int num_ctc=0;
vector <int> ::iterator it;
void first_DFS( int node )
{
seen[node] = 1;
for ( int i = 1 , l = v1[node].size() ; i < l ; i++ )
{
int nnode = v1[node][i];
if ( seen[nnode] != 0 )
continue;
first_DFS(nnode);
}
st.push(node);
}
void second_DFS( int node )
{
seen[node] = 1;
for ( int i = 1 , l = v2[node].size() ; i < l ; i++ )
{
int nnode = v2[node][i];
if( seen[nnode] == -1 )
continue;
second_DFS(nnode);
}
v3[num_ctc].push_back(node);
}
int main()
{
f >> n >> m;
while ( m-- )
{
f >> x >> y;
v1[x].push_back(y);
v2[y].push_back(x);
}
for ( int i = 1 ; i <= n ; i++ )
if( !seen[i] )
first_DFS( i );
while ( !st.empty())
{
if(seen[st.top()] == -1 )
{
st.pop();
continue;
}
num_ctc++;
second_DFS(st.top());
st.pop();
}
g << num_ctc << "\n";
for ( int i = 1 ; i <= n ; i++ )
{
for ( it=v3[i].begin() ; it != v3[i].end() ; it ++ )
g << *it << " ";
g << '\n';
}
return 0;
}